\documentclass[oneside,a4paper,12pt]{article}%TODO sprawdzic czy twoside zaczyna od dobrej strony - strona tytulowa
%\documentclass[twoside,a4paper,12pt]{article}
%TODO draft, openright?
\usepackage[utf8x]{inputenc}

\usepackage{lineno}%line numbers

%\usepackage{sudoku}
\usepackage{array}%array row width

%\pdfoutput=0 % for dvi output

\usepackage{ifpdf}%for ifpdf command

%TODO !!! psuje generacje dvi !!!
%\ifpdf%\ifx\pdftexversion\undefined
%\usepackage[dvips]{graphicx}
%\else
%\usepackage[pdftex]{graphicx}% needed for figures%line numbers
%\usepackage{epstopdf} - nie dziala
%\DeclareGraphicsRule{*}{mps}{*}{}
%\fi
\usepackage{graphicx}  % needed for figures%line numbers

\usepackage{dcolumn}   % needed for some tables%line numbers
\usepackage{bm}        % for math%line numbers
\usepackage{amssymb}   % for math%line numbers

\usepackage{verbatim} %do kilkuliniowych komentarzy
\usepackage{amsmath}%do wzorow funkcji w kilku liniach

%\usepackage{uml}%UML but only latex, no pdflatex support


%\usepackage{polski}
\usepackage[T1]{fontenc}
\usepackage[polish, english]{babel}

%\usepackage{anysize} %do marginsesow
%\marginsize{3cm}{2cm}{2cm}{2cm}

\usepackage[left=3cm,right=2cm,top=3.25cm,bottom=3.05cm]{geometry}%do marginsesow

\usepackage{setspace}
\setstretch{1.4}
%\singlespacing
%\onehalfspacing

\raggedbottom%force top align - bez justowania w pionie dla twoside

\usepackage{listings}%listingi
\usepackage{xcolor}
\usepackage{textcomp}
\definecolor{listinggray}{gray}{0.9}
\definecolor{lbcolor}{rgb}{0.9,0.9,0.9}
\lstset{
	backgroundcolor=\color{lbcolor},
	tabsize=4,
	rulecolor=,
	language=c++,
        basicstyle=\scriptsize,
        upquote=true,
        aboveskip={1.5\baselineskip},
        columns=fixed,
        showstringspaces=false,
        extendedchars=true,
        breaklines=true,
        prebreak = \raisebox{0ex}[0ex][0ex]{\ensuremath{\hookleftarrow}},
        frame=single,
        showtabs=false,
        showspaces=false,
        showstringspaces=false,
        identifierstyle=\ttfamily,
        keywordstyle=\color[rgb]{0,0,1},
        commentstyle=\color[rgb]{0.133,0.545,0.133},
        stringstyle=\color[rgb]{0.627,0.126,0.941},
}



\usepackage{tikz}

\usepackage{rccol}%for numbers align in tables
%\usepackage{subfig}%for horizontal many tables or figures, not used

\frenchspacing
\usepackage{indentfirst}

%\DeclareGraphicsExtensions{.eps,.pdf,.png,.jpg}%image order for pdflatex

\graphicspath{{./..}}%specify path for pictures

\usepackage{emp}%UML diagrams


\makeatletter%małpy
\newcommand{\linia}{\rule{\linewidth}{0.4mm}}

%pie chart
\newcommand{\slice}[4]{
  \pgfmathparse{0.5*#1+0.5*#2}
  \let\midangle\pgfmathresult

  % slice
  \draw[thick,fill=blue!50] (0,0) -- (#1:1) arc (#1:#2:1) -- cycle;

  % outer label
  \node[label=\midangle:#4] at (\midangle:1) {};

  % inner label
  %\pgfmathparse{min((#2-#1-10)/110*(-0.3),0)}
  %\let\temp\pgfmathresult
  %\pgfmathparse{max(\temp,-0.5) + 0.8}
  %\let\innerpos\pgfmathresult
  %\node at (\midangle:\innerpos) {#3};
}


\renewcommand{\maketitle}
{
  \begin{titlepage}

    \begin{center}
      POLITECHNIKA ŁÓDZKA\\
      Wydział Elektrotechniki, Elektroniki, \\
      Informatyki i Automatyki

    \vspace{3cm}

    Praca dyplomowa magisterska

    \noindent\linia

      \LARGE \textsc{\@title} \\
      
     \noindent\linia \\
      \normalsize \textsc{\@author} \\
      Nr albumu: 131572
    \end{center}

    \vspace{0.5cm}

    \begin{flushright}
      \vspace{\stretch{2}}
      {\small Opiekun pracy:}\\
      dr inż. Mariusz Zubert
    \end{flushright}

    \vspace*{\stretch{6}}

    \centering
    Łódź, \@date

  \end{titlepage}
}

%TODO polskie znaki na wykresach
%TODO sprawdzic aktualnosc rysunkow i listingow
%TODO listingi na float?
%TODO ilość -> liczba - zrobione
%TODO aktualizacja diagramow klas i listingow

\title{Zastosowanie programowania ewolucyjnego do rozwiązywania klasy problemów NP-zupełnych}
\author{Łukasz Szybka}
\date{2010}


\usepackage{fancyhdr}
\setlength{\headheight}{25.3pt}%{15.2pt}
\pagestyle{fancy}

\fancyhf{}
\lhead{\small \hspace{7.5pt}\@author \\}
\rhead{\small \@title   }
%\rfoot{\thepage}
\lfoot[\thepage]{}%twoside
\rfoot[]{\thepage}%twoside

\makeatother%małpy


\usepackage[bookmarks=true]{hyperref}%\usepackage[pdftex,bookmarks=true]{hyperref}%dvips
\hypersetup{%
    pdftitle={The application of evolution programming to solve NP-complete class problems.},
    pdfauthor={Lukasz Szybka},
    pdfsubject={The application of evolution programming to solve NP-complete class problems.},
    %pdfcreator
    %pdfproducer
    pdfkeywords={genetic, algorithm, computation, evolution},
    bookmarksnumbered,
    pdfstartview={FitH},
    pdfpagemode={UseOutlines},
    unicode=true,
   % pdfborder={0 0 0},
    colorlinks=true,
    %colorlinks=false,
    %linkcolor=black,
    linkcolor=blue,
    %urlcolor=black,
    urlcolor=cyan,
    %citecolor=black,
    citecolor=green,
    bookmarksopen=true,
}%

\usepackage[acronym, nonumberlist]{glossaries}%słownik pojęć

%\usepackage[style=altlist,
%nonumberlist,
%numberedsection,
%acronym,
%toc]
%{glossaries}

\makeglossaries

\usepackage[polish]{nomencl}%nomenklatura
\makenomenclature


%\setcounter{tocdepth}{4}%glebokosc spisu tresci


%zmiana tytulu tabel
 \AtBeginDocument{%
        \addto\captionspolish{%
        \renewcommand{\tablename}{Tabela}%
 }} 


\begin{document}
\begin{empfile}%needed for UML metapost
\begin{empcmds}%needed for UML metapost
input metauml;%needed for UML metapost
\end{empcmds}%needed for UML metapost



%\setpagewiselinenumbers%line numbers
%\modulolinenumbers[1]%line numbers
%\linenumbers%line numbers

\selectlanguage{polish}

\begin{titlepage}
 \maketitle
\end{titlepage}

%\stepcounter{page}%zwieksz numer strony, twoside
%\addtocounter{page}{-1}%twoside

\begin{abstract}
Praca przedstawia niedeterministyczne podejście do rozwiązywania problemów optymalizacji wielokryterialnej, w tym także NP-zupełnych. Inspiracją dla wyboru tematu było zainteresowanie autora alternatywnymi algorytmami, które pozwalają łączyć zagadnienia typowo informatyczne z innymi gałęziami nauki jak genetyka czy ewolucjonizm oraz wykorzystywać procesy zachodzące w naturze od wieków.

Pierwotnym celem pracy była chęć sprawdzenia, czy pseudolosowy algorytm może w praktyce skutecznie rozwiązywać konkretne problemy, oraz jaka jest jego skuteczność. W tym celu autor opracował bibliotekę, zapewniającą wszystkie podstawowe mechanizmy algorytmów genetycznych, którą można łatwo rozszerzać o dodatkową funkcjonalność i dostosowywać do rozwiązywania nowych zagadnień.

Praca podzielona jest na siedem rozdziałów poprzedzonych wstępem. Rozdział \ref{sec:genetic_algorithms} zawiera szczegółowy opis algorytmów genetycznych oraz schemat ich działania. W rozdziale \ref{sec:genetic_algorithms_theory} przedstawiono niektóre zagadnienia z teorii oraz wyjaśniono procesy sprawiające, że algorytmy genetyczne są skuteczne. Opis biblioteki, zawierającej cały mechanizm algorytmu genetycznego dla dowolnego problemu, zawiera rozdział \ref{sec:library_description}. Kilka diagramów klas oraz listingi najważniejszych fragmentów kodu, pozwalają zrozumieć sposób realizacji algorytmu genetycznego, wybrany przez autora. Biblioteka umożliwia sterowanie algorytmem za pomocą wielu parametrów. Analiza najlepszych wartości tych parametrów na konkretnych przykładach znajduje się w rozdziale \ref{sec:environment_parameters_analysis}. W rozdziale \ref{sec:optimization} zaprezentowano działanie algorytmu dla kilku funkcji dwóch zmiennych, co pozwala na dobrą graficzną prezentację wyników. W rozdziale \ref{sec:np_complete_problems} opisano zastosowanie biblioteki do rozwiązania problemów NP-zupełnych wraz z wynikami działania i ich analizą. Podsumowanie i wnioski znajdują się w rozdziale \ref{sec:conclusion}. Lista symboli wykorzystywanych w pracy a także słownik pojęć związanych z algorytmami genetycznymi znajduje się na końcu pracy.

\end{abstract}
\pagebreak

\begin{otherlanguage}{english}

  \begin{abstract}
 
Thesis concerns nondeterministic approach to solve multiobjective optimization problems, including NP-complete.
The inspiration for the choice of subject was the author's interest in alternative algorithms that allows to connect a typical IT issues with other branches of science such as genetics and evolution theory.

The primary purpose of this study was to determine whether the pseudorandom algorithm can effectively solve specific practical problems, and what is its effectiveness. To achieve that goal, the author has developed a library, providing all the basic mechanisms of genetic algorithms that can be easily extended with additional functionality and adapt to solve new problems.

Thesis is divided into seven chapters, preceded by an introduction. Chapter \ref{sec:genetic_algorithms} contains a detailed description of genetic algorithms. Chapter \ref{sec:genetic_algorithms_theory} presents some theory about genetic algorithms and contains explanaition of the processes that make genetic algorithms effective. Description of the designed library, which contains the entire mechanism of genetic algorithm for any problem, is in chapter \ref{sec:library_description}. Several class diagrams and listings of most important pieces of code provides possibility to understand how genetic algorithm was implemented. Library lets you control algorithm by using multiple parameters. Analysis of the best values of these parameters is in chapter \ref{sec:environment_parameters_analysis}. Chapter \ref{sec:optimization} presents results of optimisation of several functions of two variables using genetic algorithm. Chapter \ref{sec:np_complete_problems} describes how to use the library to solve NP-complete problems together with the results of their analysis. Chapter \ref{sec:conclusion} contains summary and conclusions. List of symbols used in the thesis, and a glossary of terms related to genetic algorithms is located at the end of work.

  \end{abstract}
\pagebreak
\end{otherlanguage}

\tableofcontents
\pagebreak

%pojęcia
\newglossaryentry{chromosom}
{name=chromosom,
 description={Zawiera \gls{ciagkodowy} oraz wartość funkcji oceny dla tego ciągu}
}

\newglossaryentry{ciagkodowy}
{name=ciąg kodowy,
 description={Ciąg symboli o określonej długości (np. liczb binarnych, rzeczywistych), który po odpowiednim rozkodowaniu daje informację o pewnym rozwiązaniu zadania}
}

\newglossaryentry{populacja}
{name=populacja,
 description={Określa aktualne \gls{pokolenie} a także dodatkowe informacje, np. numer \glslink{pokolenie}{pokolenia} - czyli wiek populacji. W ramach populacji tworzone są nowe \glslink{pokolenie}{pokolenia}}
}

\newglossaryentry{pokolenie}
{name=pokolenie,
 description={Patrz \gls{generacja}}
}

\newglossaryentry{generacja}
{name=generacja,
 description={Zbiór \glslink{chromosom}{chromosomów} o określonej wielkości}
}

\newglossaryentry{naporselekcyjny}
{name=napór selekcyjny,
 description={Określa proporcje prawdopodobieństwa reprodukcji. Duży napór selekcyjny oznacza, że reprodukcji będą ulegać tylko najlepiej przystosowane \glslink{chromosom}{chromosomy}. Mały napór selekcyjny oznacza, że prawdopodobieństwo reprodukcji dla wszystkich \glslink{chromosom}{chromosomów} będzie zbliżone}
}

\newglossaryentry{rozwiazaniesuboptymalne}
{name=rozwiązanie suboptymalne,
 description={Rozwiązanie, które jest dobre w pewnym otoczeniu rozwiązań gorszych, jednak nie jest to rozwiązanie najlepsze wśród wszystkich możliwych rozwiązań}
}

\newglossaryentry{zbieznosc}
{name=zbieżność,
 description={Proces polegający na ciągłym poprawianiu rozwiązania i systematycznego zbliżania się do rozwiązania optymalnego}
}

\newglossaryentry{pulapkaewolucyjna}
{name=pułapka ewolucyjna,
 description={Sytuacja kiedy algorytm jest \glslink{zbieznosc}{zbieżny} do \glslink{rozwiazaniesuboptymalne}{rozwiązania suboptymalnego}}
}

\newglossaryentry{reprezentacja}
{name=reprezentacja,
 description={Sposób przedstawienia informacji charakterystycznej dla danego problemu w \glslink{chromosom}{chromosomie}}
}

\newglossaryentry{schemat}
{name=schemat,
 description={patrz rozdział \ref{sec:schema_definition}}
}

\newglossaryentry{duplikat}
{name=duplikat,
 description={\Gls{chromosom} o identycznym \glslink{ciagkodowy}{ciągu kodowym} jak inny \gls{chromosom} w \glslink{populacja}{populacji}}
}


%TODO makeindex magisterka.nlo -s nomencl.ist -o magisterka.nls

%\let\stdsection\section
%\def\section*#1{\stdsection{#1}}
\renewcommand{\nomname}{Wykaz użytych w pracy symboli i oznaczeń}
\printnomenclature
\label{sec:nomenclature}
%\let\section\stdsection
\pagebreak


\section{Wstęp}
XXI wiek można określić mianem wieku informacji. W ostatnich latach teoria informacji i informatyka rozwijają się bardzo prężnie a moc obliczeniowa komputerów stale wzrasta. Coraz doskonalsze algorytmy informatyczne pozwalają na rozwiązywanie wielu problemów nauki i techniki a także na odkrywanie praw rządzących przyrodą. Istnieje jednak grupa problemów z którymi komputery nie radzą sobie tak dobrze jak człowiek. Są to problemy, dla których trudno znaleźć skuteczny i szybki algorytm dlatego wymagają nietypowego podejścia.

Istnieją trzy grupy metod obliczeniowych wspólnie określanych mianem inteligencji obliczeniowej (ang. {\it Computational intelligence} \cite{computational_intelligence}):
\begin{itemize}
 \item Sieci neuronowe
 \item Logika rozmyta
 \item Algorytmy genetyczne
\end{itemize}
Niniejsza praca podejmuje temat algorytmów genetycznych.
W wielu przypadkach typowe algorytmy liniowe nie sprawdzają się lub są mało skuteczne. Często wymogiem jest znalezienie dobrego rozwiązania pewnego zagadnienia w określonym czasie - jednak nie zawsze musi to być rozwiązanie najlepsze z możliwych. Losowe przeszukanie przestrzeni możliwych rozwiązań nie daje gwarancji uzyskania dobrego wyniku. Takie przypadki zachęcają do wykorzystania mechanizmów wypracowanych przez ewolucję. Algorytmy genetyczne są taką właśnie próbą. Pozwalają łączyć losowe zmiany i elementy ewolucji z algorytmami komputerowymi.

Celem pracy jest sprawdzenie skuteczności algorytmów genetycznych na konkretnych przykładach i udowodnienie, że mogą być przydatne także dla problemów NP-zupełnych.
W ramach prowadzonych prac autor niniejszej pracy postawił następujące tezy:

\newtheorem{tw1}{Teza}
\begin{tw1}
\label{teza1}
Możliwe jest opracowanie uniwersalnej biblioteki obliczeń genetycznych, która może być wykorzystana do rozwiązywania różnorodnych zagadnień.
\end{tw1}

\begin{tw1}
\label{teza2}
Możliwe jest zastosowanie algorytmów genetycznych do rozwiązywania problemów NP-zupełnych.
\end{tw1}

%TODO opis metod inteligentnych, rysunek 3 okręgi?

\pagebreak

\section{Algorytmy genetyczne}
\label{sec:genetic_algorithms}
\subsection{Cechy algorytmów genetycznych}

Algorytm genetyczny to sposób poszukiwania najlepszego rozwiązania, czerpiący z występujących w naturze procesów ewolucyjnych takich jak dobór naturalny oraz dziedziczenie. Wirtualna \gls{populacja}\footnote{Objaśnienia pojęć specyficznych dla algorytmów genetycznych znajdują się na stronie \pageref{sec:glossary} } zawiera zbiór potencjalnych rozwiązań badanego zagadnienia. Ocena rozwiązań pozwala wybrać te, które najlepiej spełniają warunki zadania i umożliwia im przejście do kolejnego pokolenia. Wymiana części informacji (krzyżowanie) umożliwia tworzenie osobników zawierających najlepsze cechy swoich rodziców. Losowa zmiana części informacji (mutacja) pozwala na wprowadzenie do \glslink{populacja}{populacji} nowych cech \cite{goldberg}.

%TODO metody optymalizacji, rozwiązania lokalne - opisać
W porównaniu do tradycyjnych metod optymalizacji zaletą algorytmów genetycznych jest to, że przetwarzają jednocześnie wiele możliwych rozwiązań, co pozwala uniknąć znalezienia extremów lokalnych. Analiza dużej liczby osobników pozwala znaleźć obszary, w których leżą rozwiązania lepsze od innych. Selekcjonowane obszarów dobrego przystosowania umożliwia natomiast na stopniowe zbliżanie się do rozwiązania najlepszego globalnie.

%TODO Zubert wszystkich ... kiedy ?
Klasyczne metody przeszukiwania wszystkich możliwych rozwiązań, opierające się na losowości, przestają być skuteczne kiedy wzrasta rozmiar problemu. Algorytmy genetyczne także wykorzystują losowość, jednak proces przeszukiwania jest ukierunkowany. Algorytmy genetyczne działają nawet dla zadań, gdzie sprawdzenie wszystkich możliwych rozwiązań w czasie krótszym niż życie przeciętnego człowieka przekracza możliwości współczesnych komputerów. Znalezienie rozwiązania bliskiego optymalnemu za pomocą algorytmów genetycznych często jest bardzo szybkie w porównaniu do sprawdzenia wszystkich rozwiązań.

\subsection{Reprezentacja i kodowanie danych w chromosomie}
Algorytm genetyczny wykorzystuje ściśle określoną strukturę danych jaką jest \gls{chromosom}. Problem, który ma być rozwiązywany musi zostać odpowiednio zakodowany w chromosomie.
Określenie dobrej \glslink{reprezentacja}{reprezentacji} jest bardzo ważnym elementem procesu projektowania algorytmu genetycznego i może mieć znaczący wpływ na jego wydajność. Należy tak dobrać kodowanie aby \gls{chromosom} był możliwie krótki i odzwierciedlał równomiernie cały obszar poszukiwań, dzięki czemu uzyskamy szybsze działanie.

Najprostszym a jednocześnie skutecznym sposobem \glslink{reprezentacja}{reprezentacji} problemu w \glslink{chromosom}{chromosomie} jest jego przedstawienie jako ciągu liczb binarnych (tabela \ref{tb:example_chromosome_binary}). Takie kodowanie umożliwia łatwe określenie krzyżowania oraz mutacji. Problemem może być jednak odpowiednie przekształcenie rozwiązań zadania na postać binarną.

\begin{table}[!ht]
  \caption{Przykładowy chromosom - reprezentacja binarna}
  \label{tb:example_chromosome_binary}
  \begin{center}
      \begin{tabular}{ | l | l |l |l |l |l |l |l |l |}
      \hline
      1&0&1&1&0&1&0&0&1\\ \hline
      \end{tabular}
  \end{center}
\end{table}

W niektórych zadaniach bardziej naturalnym sposobem \glslink{reprezentacja}{reprezentacji} może być ciąg liczb całkowitych lub rzeczywistych (tabela \ref{tb:example_chromosome_float}). Taki sposób \glslink{reprezentacja}{reprezentacji} pozwala uniknąć skomplikowanego kodowania informacji do postaci binarnej i później dekodowania rozwiązań. Trudniejsze jest jednak odpowiednie zaprojektowanie mutacji i krzyżowania. Zwykle w chromosomach zawierających liczby całkowite lub rzeczywiste określa się maksymalną i minimalną wartość, która jest wykorzystywana podczas mutacji.

\begin{table}[!ht]
  \caption{Przykładowy chromosom - reprezentacja zmiennoprzecinkowa}
  \label{tb:example_chromosome_float}
  \begin{center}
      \begin{tabular}{ | l | l |l |l |l |l |l |l |l |}
      \hline
      11.34&22.63&1.54&34.14&51.33&4.78&73.31&26.81&44.71\\ \hline
      \end{tabular}
  \end{center}
\end{table}

Jak zauważył Goldberg \cite{goldberg} kodowanie binarne ma ważną zaletę. Tabela \ref{tb:three_representation_versions} przedstawia dwie wersje kodowania tej samej informacji w chromosomie - binarnie i szesnastkowo. 

\begin{table}[!ht]
  \caption{Porównanie ciągów kodowych dla dwóch wersji kodowania}
  \label{tb:three_representation_versions}
  \begin{center}
  \begin{tabular}{c|c}
  \multicolumn{2}{c}{Kodowanie} \\  \hline
  Binarne & Szesnastkowe\\ \hline
  0000 & 0\\ \hline
  0001 & 1\\ \hline
  0010 & 2\\ \hline
  0011 & 3\\ \hline
  0100 & 4\\ \hline
  0101 & 5\\ \hline
  0110 & 6\\ \hline
  0111 & 7\\ \hline
  1000 & 8\\ \hline
  1001 & 9\\ \hline
  1010 & a\\ \hline
  1011 & b\\ \hline
  1100 & c\\ \hline
  1101 & d\\ \hline
  1110 & e\\ \hline
  1111 & f\\
  \end{tabular}
  \end{center}
\end{table}

\begin{table}[!ht]
  \caption{Zestawienie ilości ciągów kodowych i schematów dla różnych rodzajów kodowania}
  \label{tb:schema_and_code_count_comparison}
  \begin{center}
  \begin{tabular}{l|l|l}
   & kod binarny & kod szesnastkowy\\\hline
  liczba elementów alfabetu ($k$) & 2 & 16\\\hline
  długość chromosomu ($l$) & 4 & 1\\\hline
  liczba ciągów kodowych ($n_c$) & 16 & 16\\\hline
  liczba schematów ($n_s$) & \textbf{81} & \textbf{17}\\
  \end{tabular}
  \end{center}
\end{table}

W tabeli \ref{tb:schema_and_code_count_comparison} zestawiono wartości obliczone za pomocą wzorów \ref{eq:code_count} oraz \ref{eq:schema_count}. Pomimo takiej samej ilości możliwych do utworzenia ciągów kodowych dla obu \glslink{reprezentacja}{reprezentacji} liczba schematów \footnote{pojęcie schematu zostało omówione w rozdziale \ref{sec:schema_definition}} znacznie się różni. \glslink{reprezentacja}{Reprezentacja} binarna pozwala na utworzenie znacznie większej ilości schematów. Jak zauważył Goldberg \cite{goldberg} \gls{reprezentacja} binarna pozwala na utworzenie największej liczby schematów przypadających na bit informacji. Ponieważ liczba schematów jest podstawą działania algorytmów genetycznych wniosek jest taki, że kodowanie binarne jest najlepsze.

Dobierając kodowanie powinniśmy jednak zachować rozsądny bilans pomiędzy złożonością kodowania informacji w \glslink{chromosom}{chromosomie} a jego długością. Jeżeli istnieje łatwy sposób kodowania informacji w chromosomie binarnym to warto taki właśnie zastosować. Jeśli jednak przekształcanie jest skomplikowane a standardowe krzyżowanie i mutacja chromosomu binarnego tworzą chromosomy nieprawidłowe (wymagany dodatkowy algorytm naprawy) lepiej zastosować \gls{chromosom} naturalnie odzwierciedlający parametry zadania.

Istnieją także bardziej skomplikowane metody \glslink{reprezentacja}{reprezentacji} jak drzewa czy macierze (więcej informacji w \cite{michalewicz}).

\subsection{Parametry środowiska}
Środowisko, tak jak w naturalnej ewolucji, określa warunki w jakich znajduje się populacja a także jak przebiega tworzenie nowych pokoleń.
Odpowiednia regulacja parametrów środowiska pozwala znacznie poprawić działanie algorytmu a także daje możliwość dostosowania go do konkretnego problemu. Podstawowymi parametrami środowiska są:
\begin{itemize}
 \item prawdopodobieństwo krzyżowania - określa jaka część chromosomów ulega krzyżowaniu, zwykle parametr jest ustawiany na poziomie około 0.5
 \item prawdopodobieństwo mutacji - określa jak często występuje mutacja, zwykle na poziomie około 0.01
 \item liczebność \glslink{populacja}{populacji} - określa liczbę chromosomów w \glslink{populacja}{populacji} (istnieją także algorytmy genetyczne ze zmienną liczebnością populacji - w takim przypadku parametr ten określa liczebność populacji początkowej)
\end{itemize}

Można zdefiniować także dodatkowe parametry takie jak wybór metody selekcji (rozdział \ref{sec:selection_methods}) czy użycie dodatkowych modyfikacji algorytmu (rozdział \ref{sec:modifications}). Analiza najlepszych parametrów środowiska zostanie przedstawiona w kolejnych rozdziałach.

\subsection{Schemat działania algorytmu}
Zanim algorytm genetyczny zacznie działać należy wybrać odpowiednie kodowanie chromosomu oraz zdefiniować funkcję oceny, warunek zakończenia (rozdział \ref{sec:finish_condition}) i parametry środowiska.

W pierwszym kroku algorytmu następuje wybór \glslink{populacja}{populacji} początkowej (pierwsze pokolenie) o rozmiarze określonym jako parametr środowiska. W tym celu zostaje wygenerowana odpowiednia liczba chromosomów zawierających losowe cechy.

Kolejnym krokiem jest ocena chromosomów w \glslink{populacja}{populacji} za pomocą funkcji przystosowania oraz sprawdzenie warunku zakończenia. 
Jeśli warunek nie jest spełniony to za pomocą jednej z metod selekcji zostają wybrane chromosomy, które wejdą w skład nowej generacji. Następnie zostają zastosowane operatory genetyczne (krzyżowanie, mutacja) i stare pokolenie zastępowane jest aktualnym, dla którego zostaje obliczone przystosowanie osobników i cały proces się powtarza.

Poszukiwanie jest kontynuowane dopóki warunek zakończenia nie jest spełniony.
Rozwiązaniem jest osobnik o największej wartości przystosowania.
Schemat blokowy uproszczonego algorytmu genetycznego jest przedstawiony na rysunku \ref{ex:genetic_algorithm_schema}

	\begin{figure}
	  \centering
          \scalebox{0.7}
	  {
	    \input{../Schemat_blokowy_algorytmu_genetycznego}
	  }
	  \caption{Schemat blokowy algorytmu genetycznego}
	  \label{ex:genetic_algorithm_schema}
	\end{figure}

\subsection{Funkcja oceny}

Funkcja oceny (zwana także funkcją przystosowania lub dopasowania) ma za zadanie sprawdzić cechy osobników z \glslink{populacja}{populacji} i przypisać im wartości definiujące stopień w jakim spełniają warunki zadania. Przykładowa funkcja oceny może przypisywać osobnikom liczby całkowite - im większa liczba tym osobnik jest lepszym rozwiązaniem.

W całym cyklu działania algorytmu genetycznego funkcja oceny jest jedynym miejscem, w którym muszą być znane warunki zadania. Wszystkie pozostałe operacje można zrealizować w taki sposób, aby nie wiedziały jaki problem rozwiązują. Daje to możliwość łatwego dostosowania całego procesu do działania z różnymi zadaniami - wystarczy zmienić funkcję oceny.

\subsection{Modyfikacja oceny chromosomów}
\label{sec:adjust_fitness}
Poszukiwanie najlepszego rozwiązania sprowadza się do znalezienia chromosomu o największej lub najmniejszej wartości funkcji oceny \cite{goldberg}. Problem komiwojażera (rozdział \ref{sec:salesman}) wymaga minimalizacji funkcji przystosowania (znalezienie najkrótszej drogi), poszukiwanie maksimum funkcji (rozdział \ref{sec:optimization}) wymaga znalezienia \glslink{chromosom}{chromosomu} o największej wartości dopasowania. Algorytm genetyczny zwykle jest przystosowany do realizacji jednego z tych zadań, jednak zadanie minimalizacji i maksymalizacji można łatwo przekształcać, mnożąc wartość funkcji dopasowania przez minus jeden. Takie rozwiązanie prowadzi do utworzenia chromosomów o ujemnym przystosowaniu co może być niedopuszczalne dla niektórych metod selekcji, dlatego stosuje się przekształcenie funkcji oceny. Po obliczeniu oceny osobników w \glslink{populacja}{populacji} znajduje się osobnika o najmniejszym przystosowaniu $min(f)$ i przekształca wartość funkcji oceny wszystkich chromosomów według wzoru \ref{eq:adjust_fitness}.

\begin{equation}
 f'_i = f_i - min(f) \label{eq:adjust_fitness}
\end{equation}

Taka operacja zapewnia jednocześnie dodatnią wartość przystosowania oraz eliminację problemu z dodaniem stałej wartości do funkcji oceny, co jest ważne np. w selekcji metodą ruletki (rozdział \ref{sec:roulette_wheel_selection}).


\subsection{Metody selekcji}%TODO przeniesc za rozdzialy o schematach?
\label{sec:selection_methods}
Zadaniem selekcji jest wybór chromosomów do kolejnego pokolenia na podstawie wartości przystosowania, która została obliczona przez funkcję oceny. Aby uniknąć przedwczesnej \glslink{zbieznosc}{zbieżności} algorytmu do \glslink{rozwiazaniesuboptymalne}{rozwiązania suboptymalnego} selekcja nie może wybierać zawsze osobników najlepszych. Czasem musi zostać wybrany osobnik o gorszych parametrach, który może okazać się pomocny przy dalszym poszukiwaniu. Może się okazać, że w wyniku skrzyżowania osobnika o małym przystosowaniu z dobrym osobnikiem powstanie potomek lepszy niż wszystkie dotychczasowe.
W zależności od problemu można stosować różne metody selekcji, które zostaną omówione w kolejnych rozdziałach.

\subsubsection{Populacja testowa}
\label{sec:example_population}
Rozważmy prosty przykład populacji. Załóżmy, że optymalnym rozwiązaniem pewnego problemu o \glslink{reprezentacja}{reprezentacji} w chromosomie binarnym długości 20 bitów jest następujący osobnik: $10101010101010101010$ o dopasowaniu 20. Funkcja oceniająca dodaje jeden do oceny jeśli na parzystej pozycji w chromosomie znajduje się 0 a na pozycji nieparzystej 1. W tym przypadku \gls{chromosom} o dopasowaniu równym zero miałby następującą \glslink{reprezentacja}{reprezentację}: $01010101010101010101$. Opisany problem jest oczywiście bardzo prosty do rozwiązania i nie wymaga użycia algorytmu genetycznego, jednak posłuży za przykład demonstracyjny.

Utwórzmy populację początkową dla powyższego problemu o liczebności $n=5$. Tabela \ref{tb:population_example} przedstawia 5 chromosomów wraz z obliczoną funkcją oceny ($f_i$). Pozycje w ciągu kodowym nie spełniające założenia zadania zostały oznaczone na czerwono. Wartość funkcji oceny jest więc sumą pozycji nie oznaczonych kolorem czerwonym.

\begin{table}[!ht]
  \begin{center}
  \caption{Przykładowa populacja testowa $P_t$}
   \label{tb:population_example}
      \begin{tabular}{l | l | c | l|}
      \cline{2-4}
      &$i$ & \gls{ciagkodowy} & $f_i$ \\ \cline{2-4}
      &1 & \color{black}1\color{red}10\color{black}0\color{red}01\color{black}1010101\color{red}1\color{black}1\color{red}1\color{black}1010  & 14\\ \cline{2-4}
      &2 & \color{black}101\color{red}101\color{black}1\color{red}1\color{black}1\color{red}1\color{black}1\color{red}1\color{black}1\color{red}1\color{black}10\color{red}01\color{black}10  & 11 \\ \cline{2-4}
      &3 & \color{black}10\color{red}0\color{black}0\color{red}0\color{black}0\color{red}0\color{black}010\color{red}01010\color{black}01\color{red}1\color{black}1\color{red}1  & 10 \\ \cline{2-4}
      &4 & \color{red}0\color{black}0\color{red}01\color{black}1\color{red}1\color{black}10\color{red}01\color{black}1\color{red}101010\color{black}010  & 8 \\ \cline{2-4}
      &5 & \color{red}01\color{black}1\color{red}1\color{black}1\color{red}1\color{black}1\color{red}101010\color{black}0\color{red}0\color{black}01\color{red}101  & 6 \\ \cline{2-4}
      \multicolumn{1}{c}{suma}&  \multicolumn{2}{c|}{}   & 49 \\ \cline{4-4}
      \multicolumn{1}{c}{średnia}& \multicolumn{2}{c|}{}   & 9.8 \\ \cline{4-4}
      \end{tabular}
  \end{center}
\end{table}

Utworzona \gls{populacja} posłuży do prezentacji różnych metod selekcji i ich porównania.

\subsubsection{Metoda ruletki}
\label{sec:roulette_wheel_selection}
Metoda ruletki jest jedną z najbardziej powszechnych metod selekcji.
W metodzie tej wykorzystuje się wirtualną tarczę \cite{goldberg} (wykres kołowy), która jest podzielona pomiędzy poszczególne chromosomy w zależności od ich przystosowania. 
Wycinek koła, przypisany poszczególnym chromosomom, określany jest na podstawie prawdopodobieństwa obliczanego z wzoru \ref{eq:roulette_prob}:

\begin{equation}
 p_i = \frac{f_i}{\sum _{i = 1}^n f_i} \label{eq:roulette_prob}
\end{equation}


Osobnik o dobrym przystosowaniu dostaje większą część koła niż osobnik słabo przystosowany w porównaniu z resztą populacji. Tarcza ruletki zostaje podzielona według obliczonych prawdopodobieństw $p_i$. Wybrany zostaje \gls{chromosom}, któremu odpowiada wylosowane pole na tarczy.

\begin{table}[!ht]
  \begin{center}
  \caption{Populacja $P_t$ z obliczonymi wartościami do selekcji metodą ruletki}
   \label{tb:roulette_wheel_example}
      \begin{tabular}{l | l | l| R [,][.]{2}{3}| R [,][.]{3}{3}| R [,][.]{3}{3}|}
      \cline{2-6}
      &$i$ & $f_i$ &\multicolumn{1}{c|}{ $100 \cdot p_i$} & \multicolumn{1}{c|}{$pMin_i$} & \multicolumn{1}{c|}{$pMax_i$}\\ \cline{2-6}
      &1 & 14 & 28,571 &0&28,571\\ \cline{2-6}
      &2 & 11 & 22,449&28,571&51,02\\ \cline{2-6}
      &3 & 10 & 20,408&51,02&71,428\\ \cline{2-6}
      &4 & 8 & 16,327&71,428&87,755\\ \cline{2-6}
      &5 & 6 & 12,245&87,755&100\\ \cline{2-6}
      \multicolumn{1}{c}{suma}&  \multicolumn{1}{c|}{}   & 49 & 100 &\multicolumn{1}{c}{} &\multicolumn{1}{c}{}\\ \cline{3-4}
      \multicolumn{1}{c}{średnia}& \multicolumn{1}{c|}{}   & 9.8 &\multicolumn{1}{c}{} &\multicolumn{1}{c}{} &\multicolumn{1}{c}{}\\ \cline{3-3}
      \end{tabular}
  \end{center}
\end{table}

	%\begin{figure}[!ht]
	%  \centering
	%  \includegraphics[width=200px]{../chart_roulette_wheel_example}
	%  \caption{Ruletka dla populacji $P_t$ z tabeli \ref{tb:roulette_wheel_example}}
	%  \label{fig:chart_roulette_wheel_example}
	%\end{figure}

\begin{figure}[!ht]
  \centering
  \begin{tikzpicture}[scale=2]

  \newcounter{a}
  \newcounter{b}
  \foreach \p/\t in {30/\#1, 22/\#2, 20/\#3,
		    16/\#4, 12/\#5}
    {
      \setcounter{a}{\value{b}}
      \addtocounter{b}{\p}
      \slice{\thea/100*360}
	    {\theb/100*360}
	    {\p\%}{\t}
    }

  \end{tikzpicture}
  \caption{Ruletka dla populacji $P_t$ z tabeli \ref{tb:roulette_wheel_example}}
  \label{fig:chart_roulette_wheel_example}
\end{figure}

Rysunek \ref{fig:chart_roulette_wheel_example} przedstawia graficzną prezentację utworzonej ruletki. Widzimy, że \gls{chromosom} \#1 zajmuje największy wycinek koła. Praktyczną realizację kręcenia ruletką można zrealizować za pomocą losowania liczby z przedziału $[0,100)$ \cite{michalewicz}. Wybierany jest taki osobnik, że wylosowana liczba $p\in [pMin_i,pMax_i)$.

Załóżmy, że wylosowane zostały liczby: 11.423, 35.734, 82.412, 3.519, 62.877. Wybrane zostaną chromosomy jak w tabeli \ref{tb:roulette_wheel_example_selected}.

\begin{table}[!ht]
  \begin{center}
  \caption{Chromosomy wybrane za pomocą metody ruletki}
   \label{tb:roulette_wheel_example_selected}
      \begin{tabular}{|R [,][.]{2}{3} | R [,][.]{2}{3} @{,} R [,][.]{2}{3} | l |}
      \hline
      \multicolumn{1}{|c|}{Wylosowana liczba} & \multicolumn{2}{c|}{Przedział} & Chromosom \# \\ \hline
      11,423 &[0 & 28,571) &1 \\ \hline
      35,734 &[28,571 & 51,02) &2 \\ \hline
      82,412 &[71,428 & 87,755) &4 \\ \hline
      3,519 &[0 & 28,571) &1 \\ \hline
      62,877 &[51,02 & 71,428) &3 \\ \hline

      \end{tabular}
  \end{center}
\end{table}

%0  fit:  14  chromProb:  0.285714 chromDistrib:  "0.28.57142857"  expected:  1.42857 
%1  fit:  11  chromProb:  0.22449 chromDistrib:  "0.51.02040816"  expected:  1.12245 
%2  fit:  10  chromProb:  0.204082 chromDistrib:  "0.71.42857143"  expected:  1.02041 
%3  fit:  8  chromProb:  0.163265 chromDistrib:  "0.87.75510204"  expected:  0.816327 
%4  fit:  6  chromProb:  0.122449 chromDistrib:  "1.00.00000000"  expected:  0.612245 

  \subsubsection{Metoda ruletkowa - zmodyfikowana}
Metoda ruletkowa ma jedną zasadniczą wadę - jest wrażliwa na dodanie pewnej stałej do funkcji oceny \cite{arabas}.
Rozważmy dwie pomocnicze populacje $P_{t2}$ (tabela \ref{tb:roulette_wheel_modified_example_pop1}) i $P_{t2}'$ (tabela \ref{tb:roulette_wheel_modified_example_pop2}) o małej liczebności $n=3$. Populacje różnią się tylko jednym szczegółem: dla jednej z nich ($P_{t2}'$) do funkcji oceny dodano stałą wartość 100.

\begin{table}[!ht]
  \begin{center}
  \caption{Populacja $P_{t2}$ do selekcji zmodyfikowaną metodą ruletki}
   \label{tb:roulette_wheel_modified_example_pop1}
      \begin{tabular}{l | l | l| R [,][.]{2}{3}| R [,][.]{3}{3}| R [,][.]{3}{3}|}
      \cline{2-6}
      &i &  $f_i$ & \multicolumn{1}{c|}{ $100 \cdot p_i$} & \multicolumn{1}{c|}{$pMin_i$} & \multicolumn{1}{c|}{$pMax_i$}\\ \cline{2-6}
      &1 & 12 &66,667 &0&66,667\\ \cline{2-6}
      &2 & 1 &5,556 &66,667&72,222\\ \cline{2-6}
      &3 & 5 &27,778 &72,222&100\\ \cline{2-6}
      \multicolumn{1}{c}{suma}& & 18 & 100 &\multicolumn{1}{c}{} &\multicolumn{1}{c}{}\\ \cline{3-4}
      \multicolumn{1}{c}{średnia}& &  6 &\multicolumn{1}{c}{} &\multicolumn{1}{c}{} &\multicolumn{1}{c}{}\\ \cline{3-3}
      \end{tabular}
  \end{center}
\end{table}

	%\begin{figure}[!ht]
	%  \centering
	%  \includegraphics[width=200px]{../chart_roulette_wheel_modified_example_pop1}
	%  \caption{Ruletka dla populacji $P_{t2}$ z tabeli \ref{tb:roulette_wheel_modified_example_pop1}}
	%  \label{fig:chart_roulette_wheel_modified_example_pop1}
	%\end{figure}

\begin{figure}[!ht]
  \centering
  \begin{tikzpicture}[scale=2]

  \newcounter{c}
  \newcounter{d}
  \foreach \p/\t in {67/\#1, 5/\#2, 28/\#3}
    {
      \setcounter{c}{\value{d}}
      \addtocounter{d}{\p}
      \slice{\thec/100*360}
	    {\thed/100*360}
	    {\p\%}{\t}
    }

  \end{tikzpicture}
  \caption{Ruletka dla populacji $P_{t2}$ z tabeli \ref{tb:roulette_wheel_modified_example_pop1}}
  \label{fig:chart_roulette_wheel_modified_example_pop1}
\end{figure}

\begin{table}[!ht]
  \begin{center}
  \caption{Populacja $P_{t2}'$ do selekcji zmodyfikowaną metodą ruletki}
   \label{tb:roulette_wheel_modified_example_pop2}
      \begin{tabular}{l | l | l| R [,][.]{2}{3}| R [,][.]{3}{3}| R [,][.]{3}{3}|}
      \cline{2-6}
      &i &  $f_i$ & \multicolumn{1}{c|}{ $\frac{f_i}{\sum_{i=1}^n f_i}100$} & \multicolumn{1}{c|}{$pMin_i$} & \multicolumn{1}{c|}{$pMax_i$}\\ \cline{2-6}
      &1 & 112 & 35,220&0 &35,220\\ \cline{2-6}
      &2 & 101 & 31,761&35,220 &66,981\\ \cline{2-6}
      &3 & 105 & 33,019&66,981 &100\\ \cline{2-6}
      \multicolumn{1}{c}{suma}& & 318 & 100 &\multicolumn{1}{c}{} &\multicolumn{1}{c}{}\\ \cline{3-4}
      \multicolumn{1}{c}{średnia}& & 106 &\multicolumn{1}{c}{} &\multicolumn{1}{c}{} &\multicolumn{1}{c}{}\\ \cline{3-3}
      \end{tabular}
  \end{center}
\end{table}

	%\begin{figure}[!ht]
	%  \centering
	%  \includegraphics[width=200px]{../chart_roulette_wheel_modified_example_pop2}
	%  \caption{Ruletka dla populacji $P_{t2}'$ z tabeli \ref{tb:roulette_wheel_modified_example_pop2}}
	%  \label{fig:chart_roulette_wheel_modified_example_pop2}
	%\end{figure}

\begin{figure}[!ht]
  \centering
  \begin{tikzpicture}[scale=2]

  \newcounter{e}
  \newcounter{f}
  \foreach \p/\t in {35/\#1, 32/\#2, 33/\#3}
    {
      \setcounter{e}{\value{f}}
      \addtocounter{f}{\p}
      \slice{\thee/100*360}
	    {\thef/100*360}
	    {\p\%}{\t}
    }

  \end{tikzpicture}
  \caption{Ruletka dla populacji $P_{t2}'$ z tabeli \ref{tb:roulette_wheel_modified_example_pop2}}
  \label{fig:chart_roulette_wheel_modified_example_pop2}
\end{figure}

Różnica między wykresem \ref{fig:chart_roulette_wheel_modified_example_pop1} a \ref{fig:chart_roulette_wheel_modified_example_pop2} jest wyraźna. W pierwszym przypadku najlepszy osobnik zajmuje ponad 66\% ruletki, podczas kiedy w drugim przypadku zajmuje tylko niewiele ponad 35\%. Łatwo zauważyć, że dodanie stałej do funkcji oceny zatarło różnice pomiędzy osobnikami lepszymi i gorszymi.

Problem ten można jednak łatwo rozwiązać - wystarczy przed utworzeniem ruletki dla wszystkich chromosomów w \glslink{populacja}{populacji} zmniejszyć ocenę o wartość oceny najgorszego chromosomu \cite{arabas}. Metoda przekształcania wartości oceny została omówiona w rozdziale \ref{sec:adjust_fitness}. Aby uniknąć zerowego dopasowania najgorszego osobnika można wartość odejmowaną dodatkowo zmniejszyć o pewną stałą.

Możemy zmodyfikowaną metodę ruletki zastosować do testowego problemu przedstawionego w rozdziale \ref{sec:example_population}. Najmniejsza wartość dopasowania z tabeli \ref{tb:roulette_wheel_example} przypada na \gls{chromosom} \#5 i wynosi $min(f) = 6$. Aby po wprowadzeniu modyfikacji oceny \gls{chromosom} \#5 miał wartość większą od zera będziemy odejmować liczbę $min(f)-1 = 5$.

\begin{table}[!ht]
  \begin{center}
  \caption{Zmodyfikowana populacja $P_t'$}
   \label{tb:roulette_wheel_modified_example}
      \begin{tabular}{l | l | l| R [,][.]{2}{3}| R [,][.]{3}{3}| R [,][.]{3}{3}|}
      \cline{2-6}
      &$i$ & $f_i$ &\multicolumn{1}{c|}{$100 \cdot p_i$} & \multicolumn{1}{c|}{$pMin_i$} & \multicolumn{1}{c|}{$pMax_i$}\\ \cline{2-6}
      &1 & 14-5=9 & 37,5 &0&37,5\\ \cline{2-6}
      &2 & 11-5=6 & 25,0&37,5&62,5\\ \cline{2-6}
      &3 & 10-5=5 & 20,8333333&62,5&83,3333333\\ \cline{2-6}
      &4 & 8-5=3 & 12,5&83,3333333&95,8333333\\ \cline{2-6}
      &5 & 6-5=1 & 4,1666667&95,8333333&100\\ \cline{2-6}
      \multicolumn{1}{c}{suma}&  \multicolumn{1}{c|}{}   & 24 & 100 &\multicolumn{1}{c}{} &\multicolumn{1}{c}{}\\ \cline{3-4}
      \multicolumn{1}{c}{średnia}& \multicolumn{1}{c|}{}   & 4.8 &\multicolumn{1}{c}{} &\multicolumn{1}{c}{} &\multicolumn{1}{c}{}\\ \cline{3-3}
      \end{tabular}
  \end{center}
\end{table}

	%\begin{figure}[!ht]
	%  \centering
	%  \includegraphics[width=200px]{../chart_roulette_wheel_modified_example}
	%  \caption{Ruletka dla populacji z tabeli \ref{tb:roulette_wheel_modified_example}}
	%  \label{fig:chart_roulette_wheel_modified_example}
	%\end{figure}

\begin{figure}[!ht]
  \centering
  \begin{tikzpicture}[scale=2]

  \newcounter{g}
  \newcounter{h}
  \foreach \p/\t in {38/\#1, 25/\#2, 21/\#3, 12/\#4, 4/\#5}
    {
      \setcounter{g}{\value{h}}
      \addtocounter{h}{\p}
      \slice{\theg/100*360}
	    {\theh/100*360}
	    {\p\%}{\t}
    }

  \end{tikzpicture}
  \caption{Ruletka dla populacji z tabeli \ref{tb:roulette_wheel_modified_example}}
  \label{fig:chart_roulette_wheel_modified_example}
\end{figure}

Porównajmy rysunki \ref{fig:chart_roulette_wheel_example} i \ref{fig:chart_roulette_wheel_modified_example}. W wersji zmodyfikowanej \gls{chromosom} o najlepszym przystosowaniu zajmuje większy wycinek koła niż bez modyfikacji. Jest także duża różnica dla osobnika najgorszego - po modyfikacji zajmuje znacznie mniejszy wycinek tarczy.

Stosowanie zmodyfikowanej metody ruletki może być korzystne szczególnie przy końcu symulacji \cite{arabas}, kiedy w \glslink{populacja}{populacji} istnieje wiele chromosomów o wysokiej wartości funkcji oceny. Bez stosowania modyfikacji w takim przypadku zwykle ruletka jest podzielona prawie równo między chromosomy. Zmniejszenie wartości oceny wszystkich chromosomów pozwala bardziej zróżnicować podział ruletki i wybrać osobniki nieznacznie lepsze od innych.

%TODO opisac i napisac ze sie nie stosuje
%  \subsubsection{Metoda rankingowa}
\subsubsection{Metoda deterministyczna}
Metoda deterministyczna jako kryterium wyboru wykorzystuje oczekiwaną liczbę kopii chromosomu (obliczaną według wzoru \ref{eq:expected_count}).
\begin{equation}
 e_i = \frac{f_i}{\bar{f}} =\frac{f_i}{\sum_{i=1}^n f_i}n\label{eq:expected_count}
\end{equation}

gdzie $n$ określa liczebność populacji

Selekcja jest dwustopniowa \cite{goldberg}. W pierwszym kroku do nowego pokolenia przechodzi tyle kopii każdego osobnika ile wynosi część całkowita liczby $e_i$.

Następnie według wzoru \ref{eq:expected_count_modified} obliczana jest wartość $e_i'$, która równa jest ułamkowej części $e_i$.
Chromosomy zostają uporządkowane według wartości $e_i'$ a nowe pokolenie jest dopełniane osobnikami o najwyższej wartości $e_i'$.

\begin{equation}
 e_i' = e_i - \lfloor e_i \rfloor \label{eq:expected_count_modified}
\end{equation}

\begin{table}[!ht]
  \begin{center}
  \caption{Populacja $P_t$ z obliczonymi wartościami do selekcji deterministycznej}
   \label{tb:deterministic_example}
      \begin{tabular}{l | l | l| R [,][.]{1}{3}|R [,][.]{1}{3}|l|l|l|}
      \cline{2-7}
      &$i$ & $f_i$ & \multicolumn{1}{c|}{ $e_i$ } & \multicolumn{1}{c|}{$e_i'$} & $n_{t+1}$& $n_{t+1}'$\\ \cline{2-7}
      &1 & 14 & 1,428571429 & 0,428571429 & 1& 1\\ \cline{2-7}
      &2 & 11 & 1,12244898 & 0,12244898 & 1& 1\\ \cline{2-7}
      &3 & 10 & 1,020408163 & 0,020408163 & 1& 1\\ \cline{2-7}
      &4 & 8 & 0,816326531 & 0,816326531 & 0& 1\\ \cline{2-7}
      &5 & 6 & 0,612244898 & 0,612244898 & 0& 1\\ \cline{2-7}
      \multicolumn{1}{c}{suma}&  \multicolumn{1}{c|}{}   & 49 &\multicolumn{2}{c}{}\\ \cline{3-3}
      \multicolumn{1}{c}{średnia}& \multicolumn{1}{c|}{}   & 9.8 &\multicolumn{2}{c}{}\\ \cline{3-3}
      \end{tabular}
  \end{center}
\end{table}

Tabela \ref{tb:deterministic_example} prezentuje selekcję testowej populacji $P_t$. Kolumna oznaczona jako $n_{t+1}$ oznacza liczbę kopii danego osobnika, która wejdzie do nowego pokolenia po pierwszym kroku selekcji. Część całkowita wartości $e_i$ dla trzech pierwszych chromosomów wynosi 1 więc te trzy chromosomy otrzymają po jednej kopii. Kolumna oznaczona $n_{t+1}'$ oznacza liczbę kopii po drugim kroku selekcji. W tym przypadku wartości oczekiwane miały taką wartość, że każdy \gls{chromosom} uzyskał po 1 kopii w nowym pokoleniu.

Cechą charakterystyczną selekcji deterministycznej, która odróżnia ją od np. selekcji turniejowej czy ruletkowej jest to, że można przewidzieć jej wynik. Nie ma tutaj elementu losowego, selekcja uruchomiona dwa razy dla tej samej \glslink{populacja}{populacji} da zawsze taki sam wynik, co nie jest pewne w przypadku innych metod selekcji.

%TODO inny przykład

\subsubsection{Metoda turniejowa}
W turniejowej metodzie selekcji istnieje dodatkowy parametr - rozmiar turnieju. W celu wybrania jednego osobnika utworzona zostaje tymczasowa grupa chromosomów, które biorą udział w turnieju. Chromosomy wchodzące w skład turnieju losuje się z aktualnej \glslink{populacja}{populacji} aż do momentu kiedy grupa osiągnie zadany rozmiar. Następnie z grupy turniejowej wybrany zostaje \gls{chromosom} o najlepszym przystosowaniu. Ten rodzaj selekcji można łatwo modyfikować za pomocą rozmiaru turnieju \cite{michalewicz}.

Zaletą metody turniejowej jest niewrażliwość na ujemne wartości funkcji oceny a także dodanie stałej wartości do oceny wszystkich osobników.
Selekcja turniejowa z rozmiarem turnieju równym jeden jest jednoznaczna z wybraniem losowego chromosomu. Rozmiar turnieju równy rozmiarowi \glslink{populacja}{populacji} będzie powodował wybór zawsze najlepszego chromosomu z populacji. Przykładową selekcję turniejową przedstawia rysunek \ref{fig:tournament_selection_example}.

% This needs \usepackage{tikz} in the preamble
\begin{figure}
  \centering
  \begin{tikzpicture}
 %   \draw[thick,rounded corners=8pt] 
%(0,0) -- (0,2) -- (1,3.25) -- (2,2) -- (2,0) -- (0,2) -- (2,2) -- (0,0) -- (2,0);

%\draw [->,shorten <=1pt,>=angle 90,thick](3,3) -- (4,4);

\draw[arrows=->,line width=1pt](0.85,1) -- (3.25,0.3);
\draw[arrows=->,line width=1pt](0.85,-0.6) -- (3.25,-0.3);
\draw[arrows=->,line width=1pt](0.85,-1.55) -- (3.25,-0.8);

\node at (0,0) (tbl){\begin{tabular}{ | l | l |}
      \hline
      i & $f_i$ \\ \hline
      1 & 25 \\ \hline
      2 & 2 \\ \hline
      3 & 11 \\ \hline
      4 & 5 \\ \hline
      5 & 30 \\ \hline
      6 & 18 \\ \hline
      7 & 7 \\ \hline
      8 & 21 \\ \hline
      9 & 13 \\ \hline
      10 & 9 \\ \hline
      \end{tabular}};

\draw[arrows=->,line width=1pt](4.75,0) -- (7.25,0);
\node at(5.9,0.2) {sortowanie};

\node at (4,0) (tbl){\begin{tabular}{ | l | l |}
      \hline
      i & $f_i$ \\ \hline
      3 & 11 \\ \hline
      6 & 18 \\ \hline
      8 & 21 \\ \hline
      \end{tabular}};

\draw[arrows=->,line width=1pt](8.75,0) -- (11.25,0);
\node at(10.1,0.2) {wybór};
\node at(10.1,-0.2) {najlepszego};

\node at (8,0) (tbl){\begin{tabular}{ | l | l |}
      \hline
      i & $f_i$ \\ \hline
      8 & 21 \\ \hline
      6 & 18 \\ \hline
      3 & 11 \\ \hline
      \end{tabular}};

\node at (12,0) (tbl){\begin{tabular}{ | l | l |}
      \hline
      i & $f_i$ \\ \hline
      8 & 21 \\ \hline
      \end{tabular}};

  \end{tikzpicture}
  \caption{Przykład selekcji turniejowej}
  \label{fig:tournament_selection_example}
\end{figure}


%TODO wersja bez zwracania

\subsection{Operatory genetyczne}
Po wybraniu osobników do kolejnej \glslink{generacja}{generacji} zostają zastosowane standardowe operatory genetyczne z prawdopodobieństwem określonym w parametrach środowiska.
\subsubsection{Krzyżowanie}
Do krzyżowania wymagane są dwa osobniki (rodzice), które zostają dobrane w pary losowo. Następnie wybierany jest punkt krzyżowania (także losowo) i części chromosomów leżące za wylosowanym punktem zostają zamienione. W wyniku tej operacji otrzymujemy dwa osobniki potomne o wymieszanych cechach obu rodziców (tabela \ref{tb:crossover_example}).

\begin{table}[!ht]
  \begin{center}
  \caption{Przykład krzyżowania jednopunktowego}
   \label{tb:crossover_example}
      \begin{tabular}{ | l | l | l|}
      \hline
      \glslink{reprezentacja}{Reprezentacja} & binarna & zmiennoprzecinkowa\\ \hline
      Osobnik 1 & \texttt {{\color{red}101}|{\color{red}101001}}& \texttt {{\color{red}11.34 22.63  12.54}|{\color{red}34.14 51.33  4.78}}\\ \hline
      Osobnik 2 & \texttt {{\color{blue}011}|{\color{blue}001101}}& \texttt {{\color{blue}31.43 12.57 11.51}|{\color{blue}11.51 63.51  5.30}}\\ \hline
      Potomek 1 & \texttt {{\color{red}101}|{\color{blue}001101}}& \texttt {{\color{red}11.34 22.63  12.54}|{\color{blue}11.51 63.51  5.30}}\\ \hline
      Potomek 2 & \texttt {{\color{blue}011}|{\color{red}101001}}& \texttt {{\color{blue}31.43 12.57 11.51}|{\color{red}34.14 51.33 4.78}}\\ \hline
      \end{tabular}
  \end{center}
\end{table}



Możliwe są także inne warianty krzyżowania:
\begin{itemize}
 \item o jednym potomku - spośród potomków powstałych od danej pary rodziców zostaje wybrany tylko jeden
 \item wielopunktowe, w którym losowanych jest wiele punktów krzyżowania i wymienia się kilka łańcuchów
 \item wieloosobnicze - \gls{chromosom} potomny ma więcej niż dwóch rodziców
\end{itemize}

Niektóre problemy wymagają bardziej wyspecjalizowanych operatorów krzyżowania, które uwzględniają specyfikę problemu i tworzą prawidłowe chromosomy. To zagadnienie będzie omówione przy okazji konkretnych problemów.
 

\subsubsection{Mutacja}
Mutacja pozwala wprowadzić nowe cechy do populacji. Może spowodować ulepszenie osobnika lub pogorszenie jego parametrów, jednak osobnik gorzej przystosowany zostanie szybko wyeliminowany z populacji. Mutacja pozwala uniknąć sytuacji, w której wszystkie osobniki w \glslink{populacja}{populacji} zawierają taką samą cechę i nie jest możliwe uzyskanie dalszej poprawy za pomocą krzyżowania.
Mutacja zwykle modyfikuje jeden losowy bit w chromosomie zmieniając jego wartość na przeciwną. W przypadku chromosomów zmiennoprzecinkowych jedna wartość jest zastępowana przez nowo wylosowaną.

\begin{table}[!ht]
  \begin{center}
    \caption{Przykład mutacji}
      \begin{tabular}{ | l | l | l|}
      \hline
      \glslink{reprezentacja}{Reprezentacja} & binarna & zmiennoprzecinkowa\\ \hline
      przed mutacją & \texttt {101101001} & \texttt {11.34 22.63 12.54 34.14 51.33 4.78}\\ \hline
      osobnik zmutowany & \texttt {101101{\color{red}1}01} &\texttt {11.34 22.63 {\color{red}41.22} 34.14 51.33 4.78}\\ \hline
      \end{tabular}
  \end{center}
\end{table}

\subsection{Sukcesja}
Sukcesja definiuje sposób zastępowania aktualnego pokolenia przez nowe. Istnieją dwa rodzaje sukcesji\cite{arabas}:
\begin{itemize}
 \item sukcesja z całkowitym zastępowaniem - aktualne pokolenie zostaje zastąpione przez nowe, osobniki ze starego pokolenia nie wchodzą w skład nowego pokolenia.
 \item sukcesja z częściowym zastępowaniem - w skład nowego pokolenia wchodzi część osobników ze starego pokolenia oraz część nowych.
\end{itemize}


\subsection{Warunek zakończenia}
\label{sec:finish_condition}
Warunek zakończenia może być różny dla różnych zadań, istnieją jednak trzy warianty, które można zastosować dla większości problemów:

\begin{description}
 \item [Określona liczba \glslink{generacja}{generacji}] Algorytm przetwarza z góry określoną liczbę pokoleń po czym kończy działanie a najlepszy znaleziony chromosom jest rozwiązaniem. Zwykle liczba \glslink{generacja}{generacji} zależy od złożoności problemu.
  \item [Brak poprawy] Poszukiwanie jest kontynuowane dopóki w kolejnych pokoleniach są znajdowane lepsze rozwiązania. Można przyjąć przykładowo, że jeśli w ciągu ostatnich 100 \glslink{generacja}{generacji} nie znaleziono lepszego chromosomu to algorytm się kończy.
  \item [Określona wartość przystosowania] Istnieje grupa problemów, w których znamy maksymalną wartość dopasowania jaką może osiągnąć chromosom (np. Sudoku - patrz rozdział \ref{sec:sudoku}). W takim przypadku kontynuujemy poszukiwania aż do znalezienia takiego chromosomu, który jest rozwiązaniem optymalnym.
\end{description}


\subsection{Modyfikacje klasycznego algorytmu genetycznego}
\label{sec:modifications}

Do przedstawionego prostego modelu algorytmu genetycznego można oczywiście dodawać liczne modyfikacje i ulepszenia. Liczba takich zmian jest właściwie ograniczona jedynie wyobraźnią projektanta. Można także algorytm dostosować do konkretnego problemu uwzględniając jego specyfikę co może skutkować lepszą efektywnością.

Przy poszukiwaniu ulepszeń warto czerpać z mechanizmów istniejących w naturze. Opis modyfikacji można znaleźć w literaturze, np. zmienna liczebność \glslink{populacja}{populacji} czy wiek chromosomu \cite{michalewicz}.

\section{Zasada działania algorytmów genetycznych}
\label{sec:genetic_algorithms_theory}
Przedstawiony do tej pory opis algorytmów genetycznych nie wyjaśnia dlaczego właściwie takie algorytmy działają. Określone operatory genetyczne i metody selekcji opierają się w dużym stopniu na losowości. \Gls{populacja} początkowa także jest wybierana losowo. Czym więc różni się algorytm genetyczny od zwykłego błądzenia z nadzieją na znalezienie rozwiązania? Dlaczego algorytm genetyczny działa lepiej niż przeszukiwanie losowe? Jakie informacje niesie \gls{populacja} i co pozwala ukierunkować losowy proces we właściwym kierunku?

Odpowiedź na te pytania wymaga wprowadzenia kilku prostych pojęć opisujących \glslink{ciagkodowy}{ciągi kodowe} chromosomów.

\subsection{Pojęcie schematu}
\label{sec:schema_definition}
Schemat jest wzorcem umożliwiającym wyróżnienie chromosomów podobnych do siebie pod względem określonych cech \cite{goldberg} \cite{holland}. W celu omówienia schematu użyjemy \glslink{populacja}{populacji} chromosomów binarnych, pojęcie to jednak może być stosowane dla dowolnego rodzaju \glslink{reprezentacja}{reprezentacji}. Do alfabetu ${0,1}$ dodamy dodatkowy znak * określający miejsce w chromosomie, na którym może pojawić się dowolny symbol alfabetu. Ciągi kodowe tworzone w alfabecie ${0,1,*}$ nazywamy schematami \cite{goldberg}. Chromosom pasuje do schematu, jeśli na wszystkich pozycjach oznaczonych w schemacie 0 lub 1 ma odpowiednio takie same znaki. Chromosom na pozycjach oznaczonych w schemacie symbolem * może mieć dowolny znak z alfabetu.

Przykładowo do schematu 1*0*1 pasują chromosomy 10011 oraz 11001 ale nie pasują np. 00100, 11100. Do schematu ***** pasują wszystkie chromosomy o długości 5, natomiast do schematu 11100 pasuje tylko jeden chromosom.

\subsubsection{Liczba ciągów kodowych a liczba schematów}
\label{sec:schema_count}

Wzór \ref{eq:code_count} określa liczbę ciągów kodowych, które można utworzyć dla danego alfabetu i długości chromosomu, wzór \ref{eq:schema_count} określa natomiast liczbę schematów.

\begin{equation}
 n_c = k^l \label{eq:code_count}
\end{equation}

\begin{equation}
 n_s = (k + 1)^l \label{eq:schema_count}
\end{equation}

Gdzie: $l$ - długość chromosomu, $k$ - liczba elementów alfabetu, $n_c$ - liczba ciągów kodowych, $n_s$ - liczba schematów.


Przykładowo dla chromosomów binarnych o długości $l=5$ można utworzyć $2^5=32$ ciągów kodowych, ale aż $3^5=243$ schematy. 
%TODO goldberg 37


\subsubsection{Klasyfikacja schematów}
W celu klasyfikacji i porównania schematów określa się rząd oraz rozpiętość schematu \cite{goldberg}.
\paragraph{Rząd schematu}
Rząd schematu oznacza liczbę ustalonych pozycji we wzorcu, czyli pozycji nie będących *. Rząd schematu $s$ oznaczamy $o(s)$.

Kilka przykładów:

$s1 = 00*1**0**1$

$o(s1) = 5$

$s2 = *1******0*$

$o(s2) = 2$

$s3 = 00110*01*1$

$o(s3) = 8$

\paragraph{Rozpiętość schematu}
Rozpiętość schematu oznacza odległość między pierwszą i ostatnią ustaloną pozycją w schemacie. Rozpiętość schematu $s$ oznaczamy $\delta(s)$.

Kilka przykładów:

$s1 = 00*1**0**1$

$\delta(s1) = 10-1 = 9$

$s2 = *1******0*$

$\delta(s2) = 9-2 = 7$

$s3 = ****0*01**$

$\delta(s3) = 8-5 = 3$

$s4 = ******1***$

$\delta(s4) = 7-7 = 0$


\subsection{Wpływ krzyżowania na schematy}
\noindent Rozważmy chromosom:

$c1 = 0111010010$

\noindent pasujący do schematów:

$s1 = *1*******0, o(s1) = 2, \delta(s1) = 8$

$s2 = *****10***, o(s2) = 2, \delta(s2) = 1$

\noindent Załóżmy, że \gls{chromosom} c1 został skrzyżowany z chromosomem:

$c2 = 0001011101$

\noindent wylosowany został punkt krzyżowania równy 7:

$c1 = 0111010|010$

$c2 = 0001011|101$

\noindent otrzymamy chromosomy:

$c1' = 0111010|101$

$c2' = 0001011|010$

\noindent Chromosom $c1'$ nadal pasuje do schematu $s2$, natomiast nie pasuje do schematu $s1$.

Punkt krzyżowania zostaje losowo wybrany spośród $l-1 = 10-1 = 9$ pozycji. Prawdopodobieństwo, że schemat zostanie zniszczony wynosi \cite{goldberg}: $p_{dc} = p_c\frac{\delta(s)}{l-1}$ (gdzie $p_c$ oznacza prawdopodobieństwo krzyżowania), natomiast prawdopodobieństwo, że schemat przeżyje krzyżowanie przedstawia wzór \ref{crossover_schema_survive}.
\begin{equation}
 p_{sc} = 1 - p_{dc} = 1 - p_c\frac{\delta(s)}{l-1}\label{crossover_schema_survive}
\end{equation}

Schemat $s1$ jest dużo bardziej podatny na rozerwanie \cite{goldberg} ponieważ jest duże prawdopodobieństwo, że po wyborze punktu krzyżowania jego pozycje ustalone znajdą się po przeciwnych stronach punktu krzyżowania. Schemat $s1$ zostanie rozerwany jeśli punkt krzyżowania wypadnie pomiędzy pozycją 2 a 9. Prawdopodobieństwo jego przeżycia (dla $p_c = 1$) wynosi $p_{sc}(s1) = \frac{1}{9}$

Schemat $s2$ jest mało podatny na rozerwanie podczas krzyżowania. Zostanie on rozerwany tylko jeśli punkt krzyżowania wypadnie na pozycji 6. Prawdopodobieństwo jego przeżycia wynosi $p_{sc}(s1) = \frac{8}{9}$

Wniosek jest taki, że krzyżowanie często rozrywa schematy o dużej rozpiętości. Schematy o małej rozpiętości mają dużo większe szanse na przetrwanie krzyżowania.

\subsection{Wpływ mutacji na schematy}
\noindent Rozważmy chromosom:

$c1 = 0111010010$

\noindent pasujący do schematów:

$s1 = 0*11010*10, o(s1) = 8, \delta(s1) = 9$

$s2 = ****010***, o(s2) = 3, \delta(s2) = 2$

\noindent Załóżmy, że podczas mutacji zmianie uległ bit na pozycji 3, otrzymamy więc:

$c1' = 0101010010$

\noindent Chromosom $c1'$ nadal pasuje do schematu $s2$, natomiast nie pasuje do schematu $s1$.

Mutacja ma wpływ głównie na schematy wysokiego rzędu. Aby \gls{chromosom} przetrwał mutację wszystkie bity muszą pozostać niezmienione. Jeśli $p_m$ określa prawdopodobieństwo mutacji to pojedyncza pozycja w chromosomie przetrwa z prawdopodobieństwem $1-p_m$ \cite{michalewicz}. Cały \gls{chromosom} przetrwa mutację z prawdopodobieństwem $p_{sm} = (1-p_m)^{o(s)}$, ponieważ $p_m \ll 1$ to prawdopodobieństwo przetrwania można przybliżyć:

\begin{equation}
 p_{sm} = 1 - p_m o(s) \label{eq:mutation_schema_survive}
\end{equation}

%TODO wzór goldberg 47

\subsection{Twierdzenie o schematach}

\newtheorem{tw}{Twierdzenie}
\begin{tw}
Jeśli przez $m(s,t)$ określimy liczbę reprezentantów schematu s (liczbę chromosomów pasujących do schematu s) w \glslink{populacja}{populacji} w chwili $t$ to wzór \ref{eq:schema_propagation} określi oczekiwaną liczbę reprezentantów tego schematu w chwili $t+1$.
\begin{equation}
 m(s,t+1) = m(s,t)\frac{f(s,t)}{\bar{f}} \label{eq:schema_propagation}
\end{equation}
\end{tw}

gdzie $f(s,t)$ określa średnie przystosowanie wszystkich chromosomów pasujących do schematu s w chwili $t$ a $\bar{f}$ średnie przystosowanie populacji.

Z wzoru \ref{eq:schema_propagation} wynika, że schematy o przystosowaniu powyżej średniej będą miały w kolejnym pokoleniu więcej reprezentantów niż w obecnym. Po uwzględnieniu krzyżowania i mutacji według wzorów \ref{crossover_schema_survive} oraz \ref{eq:mutation_schema_survive} wzór na oczekiwaną liczbę reprezentantów przyjmie postać \cite{goldberg}:

\begin{equation}
 m(s,t+1) = m(s,t)\frac{f(s,t)}{\bar{f}}[1 - p_c\frac{\delta(s)}{l-1} - p_m o(s)] \label{eq:schema_equation}
\end{equation}
Jest to wzór określający twierdzenie o schematach, które mówi, że dobrze przystosowane schematy o małej rozpiętości i niskiego rzędu uzyskują wykładniczo rosnącą liczbę reprezentantów w kolejnych pokoleniach \cite{michalewicz}.

Schematy o małej rozpiętości i niskiego rzędu biorące udział w przetwarzaniu często nazywa się blokami budującymi. Hipoteza o blokach budujących \cite{michalewicz} mówi o tym, że algorytm genetyczny poszukuje rozwiązania bliskiego optymalnemu poprzez składanie bloków budujących.

Hipotezę o blokach budujących można porównać do tworzenia dużego obiektu za pomocą małych obiektów składowych (cegiełek).
Fakt, że liczba jednocześnie przetwarzanych przez algorytm genetyczny schematów jest dużo większa niż liczba chromosomów w \glslink{populacja}{populacji} Holland \cite{holland} nazwał wewnętrzną równoległością.


\section{Opis biblioteki}
\label{sec:library_description}
Biblioteka do obliczeń za pomocą algorytmów genetycznych została napisana w języku C++ z wykorzystaniem klas Qt. Interfejs graficzny został zaprojektowany w module Qt Designer, który wchodzi w skład środowiska programistycznego Qt Creator. W celu zapewnienia łatwych zmian kodu i zabezpieczenia przed utratą danych użyto systemu zarządzania wersjami Subversion. Dokumentacja kodu została napisana i wygenerowana zgodnie z systemem Doxygen.

Główna część biblioteki odpowiedzialna za kluczowe mechanizmy algorytmów genetycznych została zaprojektowana w taki sposób aby łatwo można było wprowadzać dodatkowe możliwości a także rozwiązywać wiele różnorodnych problemów. Rysunek \ref{fig:class_diagram} przedstawia uproszczony diagram najważniejszych klas oraz zależności między nimi.

%TODO napisac jak dodawac nowy problem do rozwiazania, jakie klasy implementowac

	\begin{figure}
	  \centering
	  \includegraphics[width=16cm]{../class_diagram}%[width=16cm, clip=true, trim=1cm 20cm 1cm 0cm]{../class_diagram}
	  \caption{Diagram klas}
	  \label{fig:class_diagram}
	\end{figure}

\subsection{Klasa Chromosome}
	\begin{figure}
	  \includegraphics[width=15cm]{../class_diagram_chromosome}
	  \caption{Diagram klasy Chromosome i klas dziedziczących}
	  \label{fig:class_diagram_chromosome}
	\end{figure}

Głównym zadaniem klasy Chromosome jest zapewnienie odpowiedniej \glslink{reprezentacja}{reprezentacji} problemu w chromosomie a także zdefiniowanie operatorów genetycznych (krzyżowanie, mutacja) specyficznych dla danego typu chromosomu. Metody odpowiedzialne za te operacje są czysto wirtualne i muszą zostać zaimplementowane osobno dla konkretnych typów chromosomów. Implementacje dla IntegerChromosome przedstawiają listingi \ref{lst:cross_over_integer} oraz \ref{lst:mutate_integer}.

Klasa zawiera także kilka metod umożliwiających porównanie chromosomów na podstawie wartości ich funkcji dopasowania (zmienna składowa {\tt fitness}). Metoda {\tt setRandom()} wypełnia \gls{chromosom} losowymi wartościami co jest potrzebne przy tworzeniu \glslink{populacja}{populacji} początkowej. Zaimplementowane zostały także metody pozwalające na dostęp do poszczególnych wartości w ciągu kodowym, pobranie długości chromosomu lub utworzenie jego \glslink{duplikat}{duplikatu}. Możliwe jest także dodanie innych operatorów genetycznych poprzez zaimplementowanie dwóch metod {\tt additionalOperators()}, ich domyślna implementacja jest pusta. Biblioteka zawiera trzy implementacje chromosomu: BinaryChromosome, IntegerChromosome oraz FloatChromosome (rysunek \ref{fig:class_diagram_chromosome_factory}) do operacji na chromosomach binarnych oraz składających się z ciągów kodowych liczb całkowitych lub rzeczywistych. Istnieje wiele problemów, w których te implementacje mogą być wykorzystane. W przypadku wymaganej dodatkowej funkcjonalności łatwo można utworzyć bardziej skomplikowane wersje.

\begin{lstlisting}[caption=Metoda crossOver() dla chromosomu liczb całkowitych, label=lst:cross_over_integer, numbers=left]
void IntegerChromosome::crossOver(const Chromosome& partner)
{
    if(this->size() != partner.size())
        qFatal("Parents lenght is different!");

    int crossOverPosition;
    crossOverPosition = (qrand() % (numberArray.size() -1)) + 1;

    for(int i=crossOverPosition;i<numberArray.size();++i)
        numberArray.replace(i, partner.at(i).toInt());

    this->setFitness(0);
}
\end{lstlisting}

\begin{lstlisting}[caption=Metoda mutate() dla chromosomu liczb całkowitych, label=lst:mutate_integer, numbers=left]
void IntegerChromosome::mutate(int index)
{
    numberArray.replace(index, getRandomIntegerValue());
}

int IntegerChromosome::getRandomIntegerValue() const
{
    double temp = minValue + (qrand() % (maxValue - minValue + 1));
    return temp;
}
\end{lstlisting}


\subsection{Klasa AbstractChromosomeFactory}
	\begin{figure}
	  \includegraphics[width=15cm]{../class_diagram_chromosome_factory}
	  \caption{Diagram klasy AbstractChromosomeFactory i klas dziedziczących}
	  \label{fig:class_diagram_chromosome_factory}
	\end{figure}
W celu łatwego zarządzania typami chromosomów zastosowano wzorzec projektowy fabryki abstrakcyjnej \cite{designpatterns}, która jest wykorzystywana do tworzenia odpowiedniego typu chromosomów o określonej długości. Fabryka może też od razu wypełnić produkowany \gls{chromosom} losowymi wartościami. Utworzenie nowej klasy chromosomu wymaga utworzenia fabryki tworzącej te chromosomy. Rysunek \ref{fig:class_diagram_chromosome_factory} przedstawia klasę AbstractChromosomeFactory wraz z implementacjami dla chromosomu binarnego i rzeczywistego.

\subsection{Klasa SelectionStrategy}

%TODO protected methods diagram klasVV
	\begin{figure}
	  \includegraphics[width=15cm]{../class_diagram_selection}
	  \caption{Diagram klas metod selekcji}
	  \label{fig:class_diagram_selection}
	\end{figure}
Literatura dotycząca algorytmów genetycznych przedstawia wiele różnych metod selekcji osobników. Biblioteka musi zapewniać możliwość łatwej zamiany sposobu selekcji. Takie możliwości daje wzorzec projektowy strategia \cite{designpatterns}. Klasa abstrakcyjna deklaruje czysto wirtualną metodę {\tt selectOne()}, która przyjmuje jako parametr listę wskaźników do chromosomu i zwraca jeden z nich. Konkretne implementacje jak selekcja turniejowa, ruletkowa czy deterministyczna definiują ciało metody. Fabryka SelectionStrategyFactory służy do produkcji odpowiedniej metody selekcji. Wyliczenie SelectionTypes pozwala określać typ, który fabryka ma wyprodukować. Listing \ref{lst:select_one_tournament} przedstawia implementację metody {\tt selectOne()} dla selekcji turniejowej, która tworzy tymczasową listę chromosomów o rozmiarze turnieju i dodaje do niej losowe chromosomy z populacji. Następnie sortuje listę względem wartości przystosowania i wybiera najlepszy chromosom. Jeśli rozmiar turnieju nie jest ustawiony, to przyjmuje wartość $\frac{1}{10}$ wielkości populacji.

\begin{lstlisting}[caption=Metoda selectOne() dla selekcji turniejowej, label=lst:select_one_tournament, numbers=left]
Chromosome* TournamentSelectionStrategy::selectOne(const QList<Chromosome*>& chromosomeList)
{
    Chromosome* chromosome;

    //if tournament size not set or too big, choose 1/10 number of chromosomes
    if(tournamentSize == 0 || tournamentSize > chromosomeList.size())
    {
        qWarning("tournament size not set or wrong!");
        tournamentSize = chromosomeList.size()/10;
    }

    QList< QPair<double, int> > tmpList;

    for(int i=0;i<tournamentSize;++i)
    {
        int index = qrand() % chromosomeList.size();
        QPair<double, int> pair(chromosomeList[index]->getFitness(), index);
        tmpList.append(pair);
    }

    qSort(tmpList.begin(), tmpList.end());

    chromosome = chromosomeList[tmpList.last().second];

    return chromosome;
}
\end{lstlisting}

\subsection{Klasa Generation}
Zadaniem klasy Generation jest przechowywanie listy chromosomów określonej długości, która reprezentuje jedno pokolenie. Chromosomy dodawane są do listy w metodzie {\tt randomChromosomes()} (listing \ref{lst:random_chromosomes}), która jako parametr przyjmuje rozmiar generacji oraz wskaźnik do odpowiedniej fabryki chromosomów. Klasa zawiera metody pozwalające dodawać nowe chromosomy do listy, metody zwracające wartość najlepszego, najgorszego i średniego przystosowania wśród chromosomów z listy. Metoda {\tt getProcreator()} (listing \ref{lst:get_procreator}) zwraca wskaźnik do jednego chromosomu z listy używając selekcji podanej jako parametr selectionStrategy. Metody {\tt performCrossOver()} (listing \ref{lst:cross_over}), {\tt performMutation()} (listing \ref{lst:mutation}) i {\tt performAdditionalOperators()} są odpowiedzialne za wywołanie metod krzyżowania, mutacji i ewentualnych dodatkowych operatorów na chromosomach z listy z prawdopodobieństwem, które jest podawane jako parametr. Operator krzyżowania/mutacji jest wywoływany jeśli wylosowana liczba z przedziału $[0,1]$ jest mniejsza niż założone prawdopodobieństwo. Jeśli chromosom zostanie wybrany do krzyżowania w metodzie {\tt performCrossOver()} to partner jest wybierany losowo z całej populacji.
Metoda {\tt findDuplicates()} zwraca listę \glslink{duplikat}{duplikatów} (identycznych chromosomów) dzięki czemu można zastosować różne metody eliminacji. Do sortowania listy według wartości przystosowania służy metoda {\tt sort()}.

\begin{lstlisting}[caption=Metoda randomChromosomes(), label=lst:random_chromosomes, numbers=left]
void Generation::randomChromosomes(int generationSize, AbstractChromosomeFactory* chromosomeFactory)
{
    for(int i=0;i<generationSize;++i)
    {
        chromosomeList.append(chromosomeFactory->getNewRandomChromosome());
    }
}
\end{lstlisting}

\begin{lstlisting}[caption=Metoda getProcreator(), label=lst:get_procreator, numbers=left]
Chromosome* Generation::getProcreator(SelectionStrategy* selectionStrategy)
{
    if(selectionStrategy == NULL)
        qFatal("NULL strategy, aborting");
    return selectionStrategy->selectOne(chromosomeList);
}
\end{lstlisting}

\begin{lstlisting}[caption=Metoda performCrossOver(), label=lst:cross_over, numbers=left]
void Generation::performCrossOver(double crossoverProb)
{
    for(int i=0;i<chromosomeList.size();++i)
    {
        if( static_cast<double>(qrand()) / static_cast<double>(RAND_MAX) <= crossoverProb)
        {
            int partnerIndex = qrand() % chromosomeList.size();
            chromosomeList[i]->crossOver(*chromosomeList[partnerIndex]);
        }
    }
}
\end{lstlisting}

\begin{lstlisting}[caption=Metoda performMutation(), label=lst:mutation, numbers=left]
void Generation::performMutation(double mutationProb)
{
    for(int i=0;i<chromosomeList.size();++i)
    {
        for(int j=0;j<chromosomeList.at(i)->size();++j)
        {
            if(static_cast<double>(qrand()) / static_cast<double>(RAND_MAX) <= mutationProb)
                chromosomeList[i]->mutate(j);
        }
    }
}
\end{lstlisting}

	\begin{figure}
	  \includegraphics[width=15cm]{../class_diagram_generation}
	  \caption{Klasa Generation}
	  \label{fig:class_diagram_generation}
	\end{figure}

\subsection{Klasa AbstractEnvironment}
Klasa AbstractEnvironment odpowiada za zarządzanie całą symulacją i utrzymywanie populacji. Najważniejszym składnikiem tej klasy jest wskaźnik {\tt currentGeneration}, który określa aktualne pokolenie. Zarządzanie populacją sprowadza się do tworzenia nowych \glslink{generacja}{generacji} i zmianę wskaźnika do aktualnej generacji. Wskaźnik {\tt solution} służy do zapamiętania najlepszego znalezionego rozwiązania w całym procesie. Wskaźnik {\tt chromosomeFactory} określa odpowiednią fabrykę chromosomów, która jest przekazywana do klasy Generation przy tworzeniu pierwszego pokolenia, natomiast wskaźnik {\tt selectionStrategy} określa metodę selekcji i jest przekazywany do klasy Generation przy wyborze chromosomów, które mają wejść w skład nowego pokolenia. Środowisko przechowuje ustawienia symulacji takie jak prawdopodobieństwo krzyżowania i mutacji, liczebność populacji, rodzaj warunku zakończenia symulacji, sposób eliminacji \glslink{duplikat}{duplikatów} (patrz rozdział \ref{sec:framework_modifications}) oraz dodatkowe modyfikacje algorytmu, które mają być użyte a także aktualny wiek populacji. Metody o nazwach rozpoczynających się od {\tt set} służą do ustawienia tych parametrów. Istnieje także kilka metod o nazwach zaczynających się na {\tt get}, które służą do pobrania rozwiązania, czasu pracy czy wieku populacji.

Metoda {\tt decodeChromosome()} pozwala zdekodować informację zawartą w chromosomie do rozwiązania problemu definiowanego przez konkretne środowisko. Jedną z najważniejszych metod jest {\tt fitnessFunction()} obliczająca wartość przystosowania dla chromosomu. Jest to metoda czysto wirtualna i musi być zaimplementowana w środowisku konkretnym, ponieważ każde środowisko inaczej ocenia chromosomy. Metoda {\tt adjustFitness()} służy do przeliczenia wartości funkcji oceny w całym pokoleniu przed przeprowadzeniem selekcji w taki sposób aby wyeliminować wartości ujemne ponieważ niektóre rodzaje selekcji działają tylko na dodatnich wartościach (np. selekcja ruletkowa i deterministyczna).

Metoda {\tt finishCondition()} (listing \ref{lst:finish_condition}) służy do sprawdzenia warunku zakończenia. Jeśli warunkiem zakończenia jest osiągnięcie zadanej liczby generacji, to porównuje wiek populacji z założoną wartością. Kiedy warunkiem zakończenia jest znalezienie chromosomu o określonej wartości funkcji dopasowania, to porównuje dopasowanie najlepszego chromosomu w aktualnej generacji z żądaną wartością za pomocą funkcji {\tt bestChromosomeFound()}.



\begin{lstlisting}[caption=Metoda finishCondition(), label=lst:finish_condition, numbers=left]
bool AbstractEnvironment::finishCondition()
{
    switch(finishConditionType)
    {
        case BestFitnessKnown:
            return bestChromosomeFound();
        case GenerationCount:
        default:
            return (getAge() >= maxGenerationsCount);
    }
}
\end{lstlisting}

Metoda {\tt performReproduction()} (listing \ref{lst:perform_reproduction}) przeprowadza tworzenie nowej generacji. Z aktualnego pokolenia wybiera odpowiednią liczbę chromosomów za pomocą jednej z zaimplementowanych metod selekcji, a następnie wywołuje metody odpowiedzialne za krzyżowanie, mutację i ewentualnie dodatkowe operatory.

\begin{lstlisting}[caption=Metoda performReproduction(), label=lst:perform_reproduction, numbers=left]
Generation AbstractEnvironment::performReproduction()
{
    Generation newGeneration;

    if(performAdjustFitness)
        adjustFitness(currentGeneration);

    while(newGeneration.size() < populationSize)
    {
        Chromosome* toAdd = currentGeneration.getProcreator(selectionStrategy);
        newGeneration.addChromosome(toAdd->duplicate());
    }

    newGeneration.performCrossOver(crossoverProb);
    newGeneration.performMutation(mutationProb);

    if(additionalOperatorProb1 + additionalOperatorProb2 > 0)
        newGeneration.performAdditionalOperators(additionalOperatorProb1, additionalOperatorProb2);

    return newGeneration;
}
\end{lstlisting}

Metoda {\tt startSimulation()} (listing \ref{lst:start_simulation}) rozpoczyna cały proces symulacji. Najpierw oblicza wartość funkcji oceny dla wszystkich chromosomów z wylosowanej populacji początkowej i ustawia pierwsze rozwiązanie na najlepszego osobnika. Następnie rozpoczyna się pętla, która działa dopóki nie zostanie spełniony warunek zakończenia. W każdej iteracji pętli tworzona jest nowa generacja i obliczana jest dla niej wartość funkcji oceny. Jeśli najlepszy chromosom z nowej generacji jest lepszy niż poprzednio znaleziony, to jest podstawiany pod rozwiązanie. W zależności od parametrów środowiska uruchamiane są dodatkowe modyfikacje algorytmu i na koniec aktualna generacja jest zastępowana nową. Kiedy symulacja się zakończy rozwiązanie można pobrać za pomocą metody {\tt getSolution()}.

\begin{lstlisting}[caption=Metoda startSimulation(), label=lst:start_simulation, numbers=left]
void AbstractEnvironment::startSimulation()
{
    countFitness(currentGeneration);

    //needed when run many times
    if(solution)
        delete solution;
    solution = currentGeneration.getBestRepresentative()->duplicate();

    while(!finishCondition())
    {
        selectionStrategy->resetTempData();

        Generation newGeneration = performReproduction();
        countFitness(newGeneration);

        if(*solution < *newGeneration.getBestRepresentative())
        {
            if(solution)
                delete solution;
            solution = newGeneration.getBestRepresentative()->duplicate();
        }

        if(abortWorseGenerations && newGeneration.totalFitness() < currentGeneration.totalFitness())
        {
            abortedGenerationsCount++;
            continue;//abort new generation when it is worse than current
        }

        //if new generation best is worst than best ever replace worst one
        if(replaceWorstRepresentative && *newGeneration.getBestRepresentative() < *solution)
            newGeneration.replaceChromosome(newGeneration.size()-1, solution->duplicate());

        if(addFreshChromosomesCount > 0)
            addFreshChromosomes(newGeneration);

        if(removeDuplicatesMethod != None)
            removeDuplicates(newGeneration);

        replaceGeneration(newGeneration);
    }
}
\end{lstlisting}

%TODO metody protectedVVV 
	\begin{figure}
	  \centering
	  \includegraphics[height=15cm]{../class_diagram_environment}
	  \caption{Klasa AbstractEnvironment}
	  \label{fig:class_diagram_environment}
	\end{figure}

\subsection{Zaimplementowane modyfikacje klasycznego algorytmu genetycznego}
\label{sec:framework_modifications}

Oprócz klasycznego algorytmu genetycznego w bibliotece istnieje kilka dodatkowych rozszerzeń, które mimo prostego działania w niektórych przypadkach znacznie poprawiają wyniki. Wszystkie te modyfikacje można wyłączyć używając metod klasy AbstractEnvironment jeżeli chcemy korzystać tylko z podstawowych cech algorytmu genetycznego.

\paragraph{Eliminacja duplikatów}
W przypadku istnienia w \glslink{populacja}{populacji} super osobnika (osobnika znacznie lepszego od innych) często dochodzi do zdominowania przez niego całej \glslink{populacja}{populacji} i znajdowanie nowych rozwiązań jest utrudnione. Skuteczną metodą zapobiegania takiej sytuacji jest wyszukiwanie identycznych osobników w populacji i ich eliminowanie. W bibliotece zostały zaimplementowane dwa rodzaje eliminacji \glslink{duplikat}{duplikatów}:
\begin{description}
 \item[Mutate] \glslink{duplikat}{duplikaty} zostaną zmutowane
 \item[Replace] \glslink{duplikat}{duplikaty} zostaną zastąpione nowymi chromosomami o losowym ciągu kodowym
\end{description}

Do ustawienia metody eliminacji \glslink{duplikat}{duplikatów} służy metoda {\tt setRemoveDuplicatesMethod()}. Podanie parametru None wyłącza eliminację \glslink{duplikat}{duplikatów}.

\paragraph{Dodawanie najlepszego dotychczasowego rozwiązania}
Modyfikacja ta polega na zastąpieniu, w każdym nowym pokoleniu, osobnika o najgorszym przystosowaniu osobnikiem, który w całym dotychczasowym procesie miał najwyższą wartość przystosowania. Taka modyfikacja tworzy dodatkową szansę reprodukcji najlepszego dotychczas osobnika z nadzieją, że może on utworzyć jeszcze lepszych potomków. Do włączenia tej opcji służy metoda {\tt setReplaceWorstRepresentative()}.

\paragraph{Dodawanie nowych chromosomów}

Dodawanie nowych chromosomów w każdej \glslink{generacja}{generacji} może prowadzić do napływu świeżej informacji genetycznej i ukierunkowania algorytmu w stronę nowych obszarów przeszukiwania. Liczbę dodawanych nowych chromosomów można ustawić za pomocą metody {\tt setAddFreshChromosomes()}. Podanie 0 jako parametr tej metody wyłącza modyfikację.

\paragraph{Pomijanie gorszych pokoleń}

Ta zmiana polega na pomijaniu nowo utworzonego pokolenia jeśli suma wartości przystosowania wszystkich chromosomów jest mniejsza niż w pokoleniu aktualnym. Taka modyfikacja niesie możliwość zapętlenia się algorytmu i działa zwykle nieefektywnie, ponieważ czasem wytworzenie gorszego pokolenia prowadzi do zmiany obszaru poszukiwań i w efekcie do znalezienia lepszego rozwiązania. Ta opcja nie jest w praktyce stosowana, można jednak ją włączyć metodą {\tt setAbortWorseGenerations()}.

\section{Analiza parametrów środowiska}
\label{sec:environment_parameters_analysis}

\subsection{Funkcje De Jonga}
\label{sec:dejong_functions}
Analiza jakości algorytmów genetycznych jest zadaniem trudnym ze względu na ich niedeterministyczny charakter. Zwykłe uruchomienie algorytmu i odczytanie wyniku nie sprawdza się, ponieważ wynik za każdym razem może być inny. Różny może być także czas znalezienia rozwiązania. De Jong \cite{dejong} w swojej pracy wprowadził zestaw 5 funkcji testowych, które są często wykorzystywane w literaturze dotyczącej algorytmów genetycznych.

\begin{equation}
 f_{DJ1} = \sum_{i=1}^3 x_i^2
\end{equation}

\begin{equation}
 f_{DJ2} = 100(x_1^2-x_2)^2 + (1-x_2)^2
\end{equation}

\begin{equation}
 f_{DJ3} = \sum_1^5 \lfloor x_i \rfloor
\end{equation}

\begin{equation}
 f_{DJ4} = \sum_1^{30} ix_i^4 + Gauss(0,1)
\end{equation}

\begin{equation}
 f_{DJ5} = \frac{1}{0.002 + \sum_{j=1}^{25} \frac{1}{j + \sum_{i=1}^2 (x_i-a_{ij})^6}}
\end{equation}

\noindent Funkcje De Jonga zostaną wykorzystane do porównania metod selekcji.

\subsection{Funkcje testowe}
\label{sec:test_functions}

Ponieważ zaimplementowany algorytm genetyczny jest przystosowany do maksymalizacji funkcji w celach testowych wykorzystamy odwrócone wersje funkcji 1,2 oraz 5 De Jonga. Dla funkcji $f_{DJ3}$ nie ma znaczenia czy rozpatrujemy maksimum czy minimum, wykorzystamy więc nie zmienioną wersję.

\begin{equation}
 f_{T1} = -f_{DJ1} = -\sum_{i=1}^3 x_i^2
\end{equation}

\begin{equation}
 f_{T2} = -f_{DJ2} = -[100(x_1^2-x_2)^2 + (1-x_2)^2]
\end{equation}

\begin{equation}
 f_{T3} = f_{DJ3} = \sum_1^5 \lfloor x_i \rfloor
\end{equation}

\begin{equation}
 f_{T5} = -f_{DJ5} = -\frac{1}{0.002 + \sum_{j=1}^{25} \frac{1}{j + \sum_{i=1}^2 (x_i-a_{ij})^6}}
\end{equation}

Wykresy funkcji testowych przedstawiono na rysunkach \ref{fig:chart_dejong-f1}, \ref{fig:chart_dejong-f2}, \ref{fig:chart_dejongf3}, \ref{fig:chart_dejong-f5}. W przypadku funkcji o wymiarze większym niż 2 na wykresach przedstawiono wersje dwuwymiarowe.

	\begin{figure}[p]
	  \centering
	  \includegraphics[width=14cm]{../DeJong-F1}
	  \caption{Wykres dwuwymiarowej wersji funkcji $f_{T1}$}
	  \label{fig:chart_dejong-f1}
	\end{figure}

	\begin{figure}[p]
	  \centering
	  \includegraphics[width=14cm]{../DeJong-F2}
	  \caption{Wykres funkcji $f_{T2}$}
	  \label{fig:chart_dejong-f2}
	\end{figure}

	\begin{figure}[p]
	  \centering
	  \includegraphics[width=14cm]{../DeJongF3}
	  \caption{Wykres dwuwymiarowej wersji funkcji $f_{T3}$}
	  \label{fig:chart_dejongf3}
	\end{figure}

	\begin{figure}[p]
	  \centering
	  \includegraphics[width=14cm]{../DeJong-F5}
	  \caption{Wykres funkcji $f_{T5}$}
	  \label{fig:chart_dejong-f5}
	\end{figure}

Przedziały, w których będziemy wykorzystywać funkcje testowe oraz wartości maksymalne w tych przedziałach zawiera tabela \ref{tb:range_max_test_function}.

  \begin{table}[!ht]
    \begin{center}
      \caption{Przedziały i wartości maksymalne funkcji testowych}
      \label{tb:range_max_test_function}
	\begin{tabular}{ | l | l | l|}
	\hline
	Funkcja & Przedział & Wartość maksymalna \\ \hline
	 $f_{T1}$& $x_i\in[-5.12;5.12]$ & $max(f_{T1}) = f_{T1}(0,0,0) = 0$ \\ \hline
	 $f_{T2}$& $x_i\in[-2.048;2.048]$ & $max(f_{T2}) = f_{T2}(1,1) = 0$ \\ \hline
	 $f_{T3}$& $x_i\in[-5.12;5.12]$ & $max(f_{T3}) = f_{T3}(x_i\in[5;5.12]) = 25$ \\ \hline
	 $f_{T5}$& $x_i\in[-65.535;65.535]$ & $max(f_{T5}) = f_{T5}(-32,-32) \approx -1$ \\ \hline
	\end{tabular}
    \end{center}
  \end{table}



\subsection{Porównanie metod selekcji}
\label{sec:selection_methods_analysis}

W celu porównania metod selekcji algorytm dla każdej z metod selekcji uruchomiono 100 razy. Wielkość \glslink{populacja}{populacji} wynosiła $n=100$, prawdopodobieństwo krzyżowania $p_c=0.9$, prawdopodobieństwo mutacji $p_m=0.05$. Rozmiar turnieju dla selekcji turniejowej wynosił $ts=10$. Warunkiem zakończenia poszukiwań było osiągnięcie 100 generacji. Wartość funkcji była obliczana dla argumentów o precyzji czterech miejsc po przecinku.

Tabele \ref{tb:optimization_dejong-f1}, \ref{tb:optimization_dejong-f2}, \ref{tb:optimization_dejongf3} oraz \ref{tb:optimization_dejong-f5} przedstawiają wyniki dla stu uruchomień algorytmu. Obliczono średnią najlepszych wyników w poszczególnych uruchomieniach, odchylenie standardowe $\mu$ od tej średniej oraz wartość bezwzględną różnicy średniego wyniku i znanego najlepszego rozwiązania.

%TODO format liczb w tabelach


  \begin{table}[!ht]
    \begin{center}
      \caption{Porównanie metod selekcji dla funkcji $f_{T1}$}
      \label{tb:optimization_dejong-f1}
	\begin{tabular}{ | l | l | l| l|}
	\hline
	selekcja & średni wynik & różnica & odchylenie standardowe $\mu$ \\ \hline
	turniejowa & -5.31014e-09 & 5.31014e-09 &2.89905e-09 \\ \hline
	deterministyczna & -0.0444119 & 0.0444119 &0.0340657 \\ \hline
	ruletkowa & -0.228875 & 0.228875 &0.184272 \\ \hline
	\end{tabular}
    \end{center}
  \end{table}

  \begin{table}[!ht]
    \begin{center}
      \caption{Porównanie metod selekcji dla funkcji $f_{T2}$}
      \label{tb:optimization_dejong-f2}
	\begin{tabular}{ | l | l | l| l|}
	\hline
	selekcja & średni wynik & różnica & odchylenie standardowe $\mu$ \\ \hline
	turniejowa & -0.00750536 &0.00750536 &0.0190803 \\ \hline
	deterministyczna & -0.00360238&0.00360238 & 0.0038875 \\ \hline
	ruletkowa & -0.0931165 &0.0931165 &0.105798 \\ \hline
	\end{tabular}
    \end{center}
  \end{table}

  \begin{table}[!ht]
    \begin{center}
      \caption{Porównanie metod selekcji dla funkcji $f_{T3}$}
      \label{tb:optimization_dejongf3}
	\begin{tabular}{ | l | l | l| l|}
	\hline
	selekcja & średni wynik & różnica & odchylenie standardowe $\mu$ \\ \hline
	turniejowa & 25 & 0 &0 \\ \hline
	deterministyczna & 20.63 & 4.37 &0.901721 \\ \hline
	ruletkowa & 17.71 & 7.29&1.72798 \\ \hline
	\end{tabular}
    \end{center}
  \end{table}

  \begin{table}[!ht]
    \begin{center}
      \caption{Porównanie metod selekcji dla funkcji $f_{T5}$}
      \label{tb:optimization_dejong-f5}
	\begin{tabular}{ | l | l | l| l|}
	\hline
	selekcja & średni wynik & różnica &odchylenie standardowe $\mu$ \\ \hline
	turniejowa & -1.04296 & 0.04296 &0.098333 \\ \hline
	deterministyczna & -1.04056 & 0.04056 &0.170521\\ \hline
	ruletkowa & -1.1468 & 0.1468 &0.31897 \\ \hline
	\end{tabular}
    \end{center}
  \end{table}

Dla wszystkich funkcji testowych widać, że metoda ruletki sprawdziła się najgorzej. Średni wynik dla selekcji ruletkowej najbardziej różni się od maksimum funkcji w danym przedziale. Także odchylenie standardowe było największe co świadczy o małej powtarzalności wyników metody.

Selekcja turniejowa w większości przypadków działała najlepiej. Dla funkcji $f_{T1}$ odchylenie standardowe jest małe w porównaniu z innymi metodami a średni wynik jest bliski optimum. Interesujący wynik uzyskała selekcja turniejowa dla funkcji $f_{T3}$, gdzie za każdym razem ze 100 uruchomień znalezione zostało rozwiązanie optymalne. Jest to spowodowane specyfiką funkcji $f_{T3}$, która osiąga maksimum dla przedziału argumentów $x_i \in [5;5.12]$.

Selekcja deterministyczna w większości przypadków uzyskała wynik niewiele gorszy od selekcji turniejowej a w przypadku funkcji $f_{T2}$ okazała się najlepsza. Dla funkcji $f_{T3}$ różnica pomiędzy selekcją deterministyczną i turniejową była pomijalnie mała.

Uzyskane wyniki są zgodne z literaturą \cite{goldberg}, w której metoda ruletkowa jest przedstawiana jako mało efektywna na tle deterministycznej czy turniejowej. Przeprowadzone badanie metod selekcji sugeruje stosowanie metody turniejowej lub deterministycznej do rozwiązywania rzeczywistych problemów, gdzie wynik nie jest znany. 

\subsection{Analiza zbieżności metod selekcji}%TODO polaczyc z poprzednim rozdzialem?

Przedstawione w rozdziale \ref{sec:test_functions} funkcje testowe posłużyły do zbadania \glslink{zbieznosc}{zbieżności} algorytmu do optimum dla różnych metod selekcji. W tym celu uruchomiono jednokrotnie algorytm dla każdej z metod selekcji z zapisem dokładnych danych dotyczących każdego pokolenia. Wielkość \glslink{populacja}{populacji} wynosiła $n=100$, prawdopodobieństwo krzyżowania $p_c=0.9$, prawdopodobieństwo mutacji $p_m=0.05$. Rozmiar turnieju dla selekcji turniejowej wynosił $ts=10$. Warunkiem zakończenia poszukiwań było osiągnięcie 100 generacji. Wartość funkcji była obliczana dla argumentów o precyzji czterech miejsc po przecinku. Otrzymane wyniki są oczywiście obarczone pewnym błędem, z powodu losowości algorytmu genetycznego, jednak nawet pojedyncze uruchomienie pozwala zauważyć różnice w metodach selekcji.

Rysunki \ref{fig:chart_dejong_simulation-f1}, \ref{fig:chart_dejong_simulation-f2}, \ref{fig:chart_dejong_simulationf3} oraz \ref{fig:chart_dejong_simulation-f5} zawierają wykresy różnicy pomiędzy najlepszym dopasowaniem w \glslink{generacja}{generacji} a rozwiązaniem optymalnym dla każdego pokolenia. Oś pionowa jest w skali logarytmicznej.

	\begin{figure}[p]
	  \centering
	  \includegraphics[width=14cm]{../optimization_DeJong-F1}
	  \caption{Porównanie zbieżności metod selekcji dla funkcji $f_{T1}$}
	  \label{fig:chart_dejong_simulation-f1}
	\end{figure}

	\begin{figure}[p]
	  \centering
	  \includegraphics[width=14cm]{../optimization_DeJong-F2}
	  \caption{Porównanie zbieżności metod selekcji dla funkcji $f_{T2}$}
	  \label{fig:chart_dejong_simulation-f2}
	\end{figure}

	\begin{figure}[p]
	  \centering
	  \includegraphics[width=14cm]{../optimization_DeJongF3}
	  \caption{Porównanie zbieżności metod selekcji dla funkcji $f_{T3}$}
	  \label{fig:chart_dejong_simulationf3}
	\end{figure}

	\begin{figure}[p]
	  \centering
	  \includegraphics[width=14cm]{../optimization_DeJong-F5}
	  \caption{Porównanie zbieżności metod selekcji dla funkcji $f_{T5}$}
	  \label{fig:chart_dejong_simulation-f5}
	\end{figure}

Dla wszystkich funkcji testowych najszybszą \glslink{zbieznosc}{zbieżnością} do rozwiązania optymalnego cechuje się selekcja turniejowa. Dla funkcji $f_{T3}$ oraz $f_{T5}$ zbiega się do rozwiązania bliskiego optimum już w pierwszych 10 pokoleniach przy czym dla $f_{T5}$ jest to rozwiązanie równe optymalnemu. Dla funkcji $f_{T1}$ dobre przybliżenie rozwiązania optymalnego uzyskano w 40 generacjach, potem widać niewielkie wahania wokół tej wartości, co może wynikać z faktu iż obliczenia wartości funkcji prowadzone są dla argumentów reprezentowanych w chromosomach z dokładnością do 4 miejsca po przecinku.

Selekcja ruletkowa i deterministyczna wypadły zdecydowanie gorzej. Na wykresach brak jest wyraźnej \glslink{zbieznosc}{zbieżności} do optimum a jedynie oscylacje wokół pewnej wartości, która dla metody deterministycznej jest mniejsza. Uzyskane wyniki potwierdzają wnioski z rozdziału \ref{sec:selection_methods_analysis}. Mała \gls{zbieznosc} selekcji deterministycznej i ruletkowej w porównaniu do turniejowej może być spowodowana stosunkowo dużym rozmiarem turnieju $ts = \frac{1}{10}n$, który gwarantuje duży \gls{naporselekcyjny}, co w przypadku podanych funkcji testowych okazało się korzystne.

\subsection{Wpływ wielkości turnieju na zbieżność selekcji turniejowej}

Selekcja turniejowa jako jedyna z przedstawionych posiada dodatkowy parametr - rozmiar turnieju, który pozwala na łatwe modyfikowanie \glslink{naporselekcyjny}{naporu selekcyjnego}. Nieodpowiedni dobór wielkości turnieju może prowadzić do zbyt wolnej \glslink{zbieznosc}{zbieżności} lub do utknięcia algorytmu w \glslink{pulapkaewolucyjna}{pułapce ewolucyjnej}. Przedstawione w rozdziale \ref{sec:test_functions} funkcje testowe posłużyły do zbadania \glslink{zbieznosc}{zbieżności} algorytmu przy różnych rozmiarach turnieju w metodzie turniejowej. Wielkość \glslink{populacja}{populacji} wynosiła $n=100$, prawdopodobieństwo krzyżowania $p_c=0.9$, prawdopodobieństwo mutacji $p_m=0.05$. Warunkiem zakończenia poszukiwań było osiągnięcie 100 generacji. Wartość funkcji była obliczana dla argumentów o precyzji czterech miejsc po przecinku. Rysunki \ref{fig:optimization_tournament_size_DeJong-F1}, \ref{fig:optimization_tournament_size_DeJong-F2}, \ref{fig:optimization_tournament_size_DeJongF3}, \ref{fig:optimization_tournament_size_DeJong-F5} prezentują wyniki dla trzykrotnego uruchomienia symulacji z rozmiarem turnieju:  $ts_1=2$, $ts_2=10$, $ts_3=50$.

	\begin{figure}[p]
	  \centering
	  \includegraphics[width=14cm]{../optimization_tournament_size_DeJong-F1}
	  \caption{Porównanie zbieżności algorytmu w zależności od wartości $ts$ dla funkcji $f_{T1}$}
	  \label{fig:optimization_tournament_size_DeJong-F1}
	\end{figure}

	\begin{figure}[p]
	  \centering
	  \includegraphics[width=14cm]{../optimization_tournament_size_DeJong-F2}
	  \caption{Porównanie zbieżności algorytmu w zależności od wartości $ts$ dla funkcji $f_{T2}$}
	  \label{fig:optimization_tournament_size_DeJong-F2}
	\end{figure}

	\begin{figure}[p]
	  \centering
	  \includegraphics[width=14cm]{../optimization_tournament_size_DeJongF3}
	  \caption{Porównanie zbieżności algorytmu w zależności od wartości $ts$ dla funkcji $f_{T3}$}
	  \label{fig:optimization_tournament_size_DeJongF3}
	\end{figure}

	\begin{figure}[p]
	  \centering
	  \includegraphics[width=14cm]{../optimization_tournament_size_DeJong-F5}
	  \caption{Porównanie zbieżności algorytmu w zależności od wartości $ts$ dla funkcji $f_{T5}$}
	  \label{fig:optimization_tournament_size_DeJong-F5}
	\end{figure}

  \begin{table}[!ht]
    \begin{center}
      \caption{Porównanie wyników symulacji z różnymi wartościami $ts$ dla funkcji $f_{T1}$}
      \label{tb:optimization_dejong-f1_tournament}
	\begin{tabular}{ | l | l | l| l|}
	\hline
	$ts$ & średni wynik & różnica &odchylenie standardowe $\mu$ \\ \hline
	3  & -1.38866e-05 & 1.38866e-05 & 2.80052e-05\\ \hline
	10  & -5.79843e-09 & 5.79843e-09 &4.04868e-09 \\ \hline
	50 & -4.57771e-09 & 4.57771e-09 & 4.96308e-24\\ \hline
	\end{tabular}
    \end{center}
  \end{table}

  \begin{table}[!ht]
    \begin{center}
      \caption{Porównanie wyników symulacji z różnymi wartościami $ts$ dla funkcji $f_{T2}$}
      \label{tb:optimization_dejong-f2_tournament}
	\begin{tabular}{ | l | l | l| l|}
	\hline
	$ts$ & średni wynik & różnica &odchylenie standardowe $\mu$ \\ \hline
	3  & -0.000333592 & 0.000333592 & 0.000719049 \\ \hline
	10  & -0.0157398& 0.0157398 &0.0358529 \\ \hline
	50 &-0.0365953 & 0.0365953 &0.10959 \\ \hline
	\end{tabular}
    \end{center}
  \end{table}

  \begin{table}[!ht]
    \begin{center}
      \caption{Porównanie wyników symulacji z różnymi wartościami $ts$ dla funkcji $f_{T3}$}
      \label{tb:optimization_dejongf3_tournament}
	\begin{tabular}{ | l | l | l| l|}
	\hline
	$ts$ & średni wynik & różnica &odchylenie standardowe $\mu$ \\ \hline
	3  &25 & 0 & 0\\ \hline
	10  &25 & 0 &0 \\ \hline
	50 & 25& 0 & 0\\ \hline
	\end{tabular}
    \end{center}
  \end{table}

  \begin{table}[!ht]
    \begin{center}
      \caption{Porównanie wyników symulacji z różnymi wartościami $ts$ dla funkcji $f_{T5}$}
      \label{tb:optimization_dejong-f5_tournament}
	\begin{tabular}{ | l | l | l| l|}
	\hline
	$ts$ & średni wynik & różnica &odchylenie standardowe $\mu$ \\ \hline
	3  & -1.01844& 0.01844 & 0.0613104\\ \hline
	10  & -1.05114& 0.05114 & 0.0896428\\ \hline
	50 & -1.06544& 0.06544 & 0.100343\\ \hline
	\end{tabular}
    \end{center}
  \end{table}

Dla funkcji $f_{T1}$ najszybciej \glslink{zbieznosc}{zbieżna} była selekcja z $ts=50$, gdzie dobre rozwiązanie zostało znalezione w około 25 \glslink{generacja}{generacjach} i po osiągnięciu tego poziomu w następnych pokoleniach nie występowało już pogorszenie najlepszego rozwiązania. Selekcja z $ts=10$ także szybko znalazła dobre rozwiązanie jednak w kolejnych pokoleniach występowały także rozwiązania gorsze, co świadczy o przeszukiwaniu nowych obszarów potencjalnych lepszych rozwiązań, które jednak w tym przypadku nie istnieją. Dla $ts=3$ proces był wolno \glslink{zbieznosc}{zbieżny} i znalezione rozwiązanie było dużo gorsze niż dla $ts=50$, czy $ts=10$, jednak widać wyraźnie trend do poprawiania rozwiązania na przestrzeni kilku pokoleń. Dla 100 uruchomień algorytmu (tabela \ref{tb:optimization_dejong-f1_tournament}) najmniejszym odchyleniem standardowym od średniej charakteryzowała się selekcja z $ts=50$ a największym z $ts=3$. Potwierdza to obserwacje z rysunku \ref{fig:optimization_tournament_size_DeJong-F1}.

Selekcja turniejowa z dużym współczynnikiem $ts$ wybiera najczęściej chromosomy o wyraźnie większym przystosowaniu co w przypadku funkcji $f_{T1}$ jest korzystne.
Dla prostej funkcji bez \glslink{pulapkaewolucyjna}{pułapek ewolucyjnych} można więc stosować duży rozmiar turnieju, który zapewnia szybką \gls{zbieznosc}.

Funkcja $f_{T2}$ prezentuje zupełnie odmienną sytuację. Algorytm z $ts=50$ i $ts=10$ utknął w \glslink{pulapkaewolucyjna}{pułapce ewolucyjnej} (odpowiednio na poziomie 0.1 i 0.01) i do końca symulacji nie poprawił wyniku. Selekcja z $ts=3$ systematycznie poprawiała najlepsze rozwiązanie przeszukując nowe obszary i ostatecznie znalazła najlepsze rozwiązanie. Symulacja z $ts=50$ i $ts=10$ miała zbyt duży \gls{naporselekcyjny} i znalazła \glslink{rozwiazaniesuboptymalne}{rozwiązania suboptymalne}. Osobniki lepsze od innych szybko zdominowały całą populację a brak nowej informacji genetycznej zatrzymał proces poprawy rozwiązania. W tabeli  \ref{tb:optimization_dejong-f2_tournament} widać, że także dla 100 uruchomień mały rozmiar turnieju sprawdził się najlepiej. Średnie znalezione rozwiązanie było znacznie lepsze niż w przypadku większych rozmiarów turnieju a także cechowało się najmniejszym odchyleniem standardowym.

Dla funkcji z wieloma \glslink{rozwiazaniesuboptymalne}{rozwiązaniami suboptymalnymi} należy więc stosować mały rozmiar turnieju.

Symulacja w przypadku funkcji $f_{T3}$ oraz $f_{T5}$ przebiegała podobnie. Dla wszystkich trzech wartości parametru $ts$ zostało znalezione dobre rozwiązanie. Algorytm ze wszystkimi trzema testowanymi rozmiarami turnieju znalazł rozwiązanie optymalne we wszystkich próbach dla funkcji $f_{T3}$.  Dla funkcji $f_{T5}$ średnio najlepiej wypadła selekcja z rozmiarem turnieju $ts=3$, miała także najmniejsze odchylenie standardowe. Mały rozmiar turnieju gwarantuje więc pewność znalezienia dobrego rozwiązania przy nieznacznie wolniejszej zbieżności.

Wniosek z przeprowadzonych obserwacji jest taki, iż rozmiar turnieju powinien być dopasowany do stopnia skomplikowania rozwiązywanego problemu. W przypadku ogólnym, kiedy nie znany jest rozkład rozwiązań i istnieją \glslink{pulapkaewolucyjna}{pułapki ewolucyjne}, należy zastosować mały rozmiar turnieju (rzędu 3 - 5) kosztem szybkości \glslink{zbieznosc}{zbieżności}. Mały rozmiar turnieju gwarantuje, że algorytm nie utknie w \glslink{rozwiazaniesuboptymalne}{rozwiązaniu suboptymalnym}.

\begin{comment}
  \subsection{Wpływ krzyżowania} %TODO porownac generacje w ktorej znaleziono?

  \begin{table}[!ht]
    \begin{center}
      \caption{Porównanie wyników symulacji z różnymi wartościami $p_c$ dla funkcji $f_{T1}$}
      \label{tb:optimization_dejong-f1_mut}
	\begin{tabular}{ | l | l | l| l|}
	\hline
	$p_c$ & średni wynik & różnica &odchylenie standardowe $\mu$ \\ \hline
	0.9  & -4.94392e-09 & 4.94392e-09 & 2.0824e-09 \\ \hline
	0.5  &  -5.31014e-09&  & 2.89905e-09 \\ \hline
	0.1  & -5.67636e-09 &  & 4.59841e-09 \\ \hline
	0.05  & -6.16464e-09  &  & 5.36424e-09 \\ \hline
	0.01  & -5.79843e-09 &  & 5.59405e-09 \\ \hline
	\end{tabular}
    \end{center}
  \end{table}

\end{comment}

\subsection{Wpływ prawdopodobieństwa mutacji na zbieżność algorytmu}
W rozdziale zbadano wpływ prawdopodobieństwa mutacji $p_m$ na \gls{zbieznosc} algorytmu. 
Algorytm został uruchomiony dla funkcji testowych z rozdziału \ref{sec:test_functions} z prawdopodobieństwami mutacji $p_{m1}=0.01$, $p_{m2}=0.05$, $p_{m3}=0.1$ oraz $p_{m4}=0.5$. Wielkość \glslink{populacja}{populacji} wynosiła $n=100$, prawdopodobieństwo krzyżowania $p_c=0.9$. Warunkiem zakończenia poszukiwań było osiągnięcie 100 generacji. Wartość funkcji była obliczana dla argumentów o precyzji czterech miejsc po przecinku. Rysunki \ref{fig:optimization_DeJong-F1_mut}, \ref{fig:optimization_DeJong-F2_mut}, \ref{fig:optimization_DeJongF3_mut} i \ref{fig:optimization_DeJong-F5_mut} prezentują wyniki przebiegu symulacji dla pojedynczego uruchomienia, natomiast tabele \ref{tb:optimization_dejong-f1_mut}, \ref{tb:optimization_dejong-f2_mut}, \ref{tb:optimization_dejongf3_mut} oraz \ref{tb:optimization_dejong-f5_mut} średni wynik, średnią różnicę między znalezionym rozwiązaniem a rozwiązaniem optymalnym oraz odchylenie standardowe najlepszych wyników od średniej dla 100 uruchomień algorytmu.

	\begin{figure}[p]
	  \centering
	  \includegraphics[width=14cm]{../optimization_DeJong-F1_mut}
	  \caption{Porównanie zbieżności algorytmu w zależności od wartości $p_m$ dla funkcji $f_{T1}$}
	  \label{fig:optimization_DeJong-F1_mut}
	\end{figure}

	\begin{figure}[p]
	  \centering
	  \includegraphics[width=14cm]{../optimization_DeJong-F2_mut}
	  \caption{Porównanie zbieżności algorytmu w zależności od wartości $p_m$ dla funkcji $f_{T2}$}
	  \label{fig:optimization_DeJong-F2_mut}
	\end{figure}

	\begin{figure}[p]
	  \centering
	  \includegraphics[width=14cm]{../optimization_DeJongF3_mut}
	  \caption{Porównanie zbieżności algorytmu w zależności od wartości $p_m$ dla funkcji $f_{T3}$}
	  \label{fig:optimization_DeJongF3_mut}
	\end{figure}

	\begin{figure}[p]
	  \centering
	  \includegraphics[width=14cm]{../optimization_DeJong-F5_mut}
	  \caption{Porównanie zbieżności algorytmu w zależności od wartości $p_m$ dla funkcji $f_{T5}$}
	  \label{fig:optimization_DeJong-F5_mut}
	\end{figure}

  \begin{table}[!ht]
    \begin{center}
      \caption{Porównanie wyników symulacji z różnymi wartościami $p_m$ dla funkcji $f_{T1}$}
      \label{tb:optimization_dejong-f1_mut}
	\begin{tabular}{ | l | l | l| l|}
	\hline
	$p_m$ & średni wynik & różnica &odchylenie standardowe $\mu$ \\ \hline
	0.01  & -4.57771e-09 & 4.57771e-09 & 4.96308e-24 \\ \hline
	0.05  & -5.43221e-09 & 5.43221e-09 & 3.11464e-09 \\ \hline
	0.1   & -1.12339e-05 & 1.12339e-05 & 1.46415e-05\\ \hline
	0.5   & -0.0740777 & 0.0740777 & 0.0536291\\ \hline
	\end{tabular}
    \end{center}
  \end{table}

  \begin{table}[!ht]
    \begin{center}
      \caption{Porównanie wyników symulacji z różnymi wartościami $p_m$ dla funkcji $f_{T2}$}
      \label{tb:optimization_dejong-f2_mut}
	\begin{tabular}{ | l | l | l| l|}
	\hline
	$p_m$ & średni wynik & różnica &odchylenie standardowe $\mu$ \\ \hline
	0.01  & -0.0639486 & 0.0639486 & 0.0884624\\ \hline
	0.05  & -0.00852182 & 0.00852182 & 0.0227884\\ \hline
	0.1   & -0.000282085 & 0.000282085 & 0.000634485\\ \hline
	0.5   & -0.0050141 & 0.0050141 & 0.00492634\\ \hline
	\end{tabular}
    \end{center}
  \end{table}

  \begin{table}[!ht]
    \begin{center}
      \caption{Porównanie wyników symulacji z różnymi wartościami $p_m$ dla funkcji $f_{T3}$}
      \label{tb:optimization_dejongf3_mut}
	\begin{tabular}{ | l | l | l| l|}
	\hline
	$p_m$ & średni wynik & różnica &odchylenie standardowe $\mu$ \\ \hline
	0.01  & 24.98 & 0.02 & 0.14\\ \hline
	0.05  & 25 & 0 & 0\\ \hline
	0.1   & 24.99 & 0.01 & 0.0994987\\ \hline
	0.5   & 19.35 & 5.65 & 0.99373\\ \hline
	\end{tabular}
    \end{center}
  \end{table}

  \begin{table}[!ht]
    \begin{center}
      \caption{Porównanie wyników symulacji z różnymi wartościami $p_m$ dla funkcji $f_{T5}$}
      \label{tb:optimization_dejong-f5_mut}
	\begin{tabular}{ | l | l | l| l|}
	\hline
	$p_m$ & średni wynik & różnica &odchylenie standardowe $\mu$ \\ \hline
	0.01  & -1.21254 & 0.21254 & 1.0089\\ \hline
	0.05  & -1.03888 & 0.03888 & 0.0866989\\ \hline
	0.1   & -1.03264 & 0.03264 & 0.081555\\ \hline
	0.5   & -1.2258 & 0.2258 & 0.371807\\ \hline
	\end{tabular}
    \end{center}
  \end{table}

W przypadku funkcji $F_{T1}$ algorytm działał najlepiej dla małego prawdopodobieństwa mutacji $p_m=0.01$. Dla prawdopodobieństw $p_m=0.05$ i $p_m=0.1$ także był \glslink{zbieznosc}{zbieżny} ale wyraźnie wolniej im większy parametr $p_m$. Dla $p_m=0.5$ algorytm przestał działać i nie znalazł rozwiązania. Mutacja występowała zbyt często i niszczyła wszystkie dobre wyniki przez co nie przechodziły one do kolejnych pokoleń i cały proces stał się błądzeniem losowym.

Prawdopodobieństwo mutacji rzędu $p_m=0.05$, $p_m=0.1$ okazało się nieznacznie lepsze niż $p_m=0.01$ dla funkcji $F_{T1}$. Ten przykład pozwala docenić wartość mutacji, która w tym przypadku przyczyniła się do poprawy rozwiązania wprowadzając nowe informacje do populacji. Prawdopodobieństwo $p_m=0.5$ było jednak zbyt duże i spowodowało złe działanie algorytmu.

Wyniki dla funkcji $F_{T3}$ i $F_{T5}$ są podobne jak dla $F_{T1}$. Algorytm działał dobrze dla małego prawdopodobieństwa mutacji i był tym szybciej \glslink{zbieznosc}{zbieżny} im to prawdopodobieństwo było mniejsze. Dla $p_m=0.5$ algorytm przestawał działać poprawnie.

Przeprowadzone badania pozwalają stwierdzić, że mutacja jest ważną częścią algorytmów genetycznych i bez niej symulacja może utknąć w \glslink{pulapkaewolucyjna}{pułapce ewolucyjnej}. Dobranie zbyt dużego prawdopodobieństwa mutacji skutkuje jednak brakiem \glslink{zbieznosc}{zbieżności}. Dla ogólnych problemów prawdopodobieństwo mutacji powinno być ustawiane na poziomie około 0.01 - 0.05.

%\subsection{Analiza liczebności populacji}%TODO


\section{Optymalizacja funkcji}
\label{sec:optimization}

\subsection{Opis aplikacji}
W przypadku optymalizacji funkcji wartości łatwo można zamienić na \glslink{reprezentacja}{reprezentację} binarną dlatego najlepszym wyborem rodzaju chromosomu jest \gls{chromosom} binarny (BinaryChromosome).
Klasa OptimizationEnvironment dziedziczy po AbstractEnvironment i korzysta z BinaryChromosomeFactory do produkcji chromosomów. Jako parametr konstruktora przyjmuje wektor zakresów zmiennych, precyzję ({\tt precision}) określającą próbkowanie zakresu zmiennych oraz wskaźnik do funkcji, którą algorytm ma optymalizować. Funkcja ta powinna przyjmować wektor argumentów, dla których ma być obliczona jej wartość. Funkcja może mieć dowolną liczbę argumentów określonych w wektorze zakresów. Parametr {\tt precision} określa, jak wiele różnych chromosomów będzie można utworzyć oraz jaka będzie ich długość.

Przykładowo dla funkcji jednej zmiennej, jeśli argument $x_1 \in (x_{1min},x_{1max})$ to liczba przedziałów na jaką zostanie podzielony zakres argumentu $x$ będzie obliczona według wzoru \cite{michalewicz}:

$N_p = (x_{1max}-x_{1min})10^{precision}$

\noindent a długość chromosomu będzie spełniała zależność:

$2^{l-1} < N_p \eqslantless 2^l$

Dla funkcji wielu zmiennych całkowita długość chromosomu jest równa sumie długości obliczonych dla poszczególnych zakresów.%TODO wzor?

Metoda {\tt fitnessFunction()} dzieli \gls{chromosom} na poszczególne argumenty funkcji i przelicza na system dziesiętny a następnie tworzy wektor argumentów i wywołuje funkcję określoną w konstruktorze OptimizationEnvironment w celu obliczenia przystosowania.
%TODO diagram klas

\subsection{Optymalizacja kilku wybranych funkcji}
Wykorzystując parametry środowiska przeanalizowane w rozdziale \ref{sec:environment_parameters_analysis} zostanie sprawdzona skuteczność algorytmu przy poszukiwaniu wartości maksymalnej kilku funkcji dwóch zmiennych o wielu \glslink{rozwiazaniesuboptymalne}{rozwiązaniach suboptymalnych}.

 W poniższych symulacjach wielkość \glslink{populacja}{populacji} wynosiła $n=100$, prawdopodobieństwo krzyżowania $p_c=0.9$, prawdopodobieństwo mutacji $p_m=0.05$. Warunkiem zakończenia poszukiwań było znalezienie rozwiązania różniącego się od znanego maksimum o mniej niż $0.0001$. Wartość funkcji była obliczana dla argumentów o precyzji czterech miejsc po przecinku.

\subsubsection{Funkcja $F_s$}
Rozpatrzmy funkcję o wzorze:

      \begin{equation}
      F_s(x,y) = 30 sinc(2x,2y) + x sin(2x) + y sin(2y) \label{eq:test_function_sinc}
      \end{equation}
      dla: $x\in[-10,10]$ oraz $y\in[-10,10]$

      gdzie:
      \[
      sinc(x,y) =
      \begin{cases}
	\frac{sin(\sqrt{x^2+y^2})}{\sqrt{x^2+y^2}} & \quad \text{dla } x\neq0 \text{ lub } y\neq0\\
	1 & \quad \text{dla } x=0, y=0\\
      \end{cases}
      \]

funkcja $F_s$ w danym przedziale osiąga maksymalną wartość dla:
$max(F_s) = F_s(0,0) = 30$

Wzór funkcji $F_s$ przedstawia wykres \ref{fig:test_function_sinc}.

      \begin{figure}[!ht]
	\includegraphics[width=16cm]{../test_function_sinc}
	\caption{Wykres funkcji $F_s$ określonej wzorem \ref{eq:test_function_sinc}}
	\label{fig:test_function_sinc}
      \end{figure}



Po uruchomieniu symulacji 100 razy średnio algorytm znajdował rozwiązanie spełniające podany warunek w \glslink{generacja}{generacji} 8.87 a odchylenie standardowe od tej średniej wynosiło 2.11969. W najgorszym ze 100 przypadków rozwiązanie zostało znalezione w 14 pokoleniu. Pomimo istnienia wielu \glslink{pulapkaewolucyjna}{pułapek ewolucyjnych} algorytm radzi sobie dobrze ze znajdowaniem maksymalnej wartości funkcji $F_s$.
Sprawdzimy teraz jaki wynik algorytm osiągnie po 100 generacjach. Po uruchomieniu symulacji z parametrami środowiska takimi, jak w poprzednim teście i warunkiem zakończenia po 100 pokoleniach najlepszy uzyskany wynik był następujący:

%-3.8147118175957395181e-05|3.8147118175957395181e-05
%fitness: 29.999999991268783361
      \begin{center}
      $x = -3.8147118175957395181e-05$\\
      $y = 3.8147118175957395181e-05$\\
      $F_s(x,y) = 29.999999991268783361$\\
      \end{center}

Jest to wynik zadowalający, znalezienie lepszego rozwiązania może być trudne ze względu na precyzję argumentów, która wynosi 4 miejsca po przecinku. Gdyby potrzebny był bardziej dokładny wynik można zastosować większą precyzję.


\subsubsection{Funkcja $F_t$}
Kolejną funkcją jest\footnote{wzór funkcji został zaczerpnięty ze strony \url{http://www.codeproject.com/KB/recipes/btl_ga.aspx}}:

      \begin{equation}
      F_t(x,y) =  [15xy(1-x)(1-y) sin(9  \pi x) sin(9 \pi y)]^2 \label{eq:test_function_sin2}
      \end{equation}
      dla: $x\in[0,1]$ oraz $y\in[0,1]$

\noindent Funkcja $F_t$ w danym przedziale osiąga maksymalną wartość dla:

$max(F_t) = F_t(0.5,0.5) = 0.87890625$

Wzór funkcji $F_t$ przedstawia wykres \ref{fig:test_function_sin2}.

      \begin{figure}[!ht]
	\includegraphics[width=16cm]{../test_function_sin2}
	\caption{Wykres funkcji $F_t$ określonej wzorem \ref{eq:test_function_sin2}}
	\label{fig:test_function_sin2}
      \end{figure}

Algorytm w 100 uruchomieniach średnio znajdował wynik w pokoleniu 25.98 a odchylenie standardowe od tej średniej wyniosło 56.576, czyli było znacznie większe niż w przypadku funkcji $F_s$. W kilku przypadkach rozwiązanie znalezione zostało w pokoleniu większym niż 200 a w najgorszym przypadku w pokoleniu 421. Widać widocznie, że funkcja $F_t$ jest trudniejsza dla algorytmu genetycznego, ponieważ istnieje wiele \glslink{rozwiazaniesuboptymalne}{rozwiązań suboptymalnych} o wartościach niewiele gorszych niż maksimum globalne. Algorytm czasem wpada w \glslink{pulapkaewolucyjna}{pułapkę ewolucyjną}, jednak pomimo tego po jakimś czasie wychodzi z niej i znajduje najlepsze rozwiązanie. W celu szybszego wychodzenia z pułapek można dokonać zmiany parametrów środowiska lub włączyć jeden z dodatków opisanych w rozdziale \ref{sec:framework_modifications}. Po uruchomieniu algorytmu na 500 \glslink{generacja}{generacji} uzyskano wynik:
%8191|8191
%0.49996948055911616393|0.49996948055911616393
%fitness: 0.87890492799048036687
%0,499969481

      \begin{center}
      $x = 0.49996948055911616393$\\
      $y = 0.49996948055911616393$\\
      $F_t(x,y) = 0.87890492799048036687$\\
      \end{center}

\subsubsection{Funkcja Easom'a}
%[Eas90] Easom, E. E.: A survey of global optimization techniques. M. Eng. thesis, Univ. Louisville, Louisville, KY, 1990.

Easom \cite{easom} w swojej pracy zaproponował następującą funkcję:

      \begin{equation}
      F_{Eas}(x,y) =  cos(x)cos(y)e^{-[(x-\pi)^2+(y-\pi)^2]} \label{eq:test_function_easom}
      \end{equation}
      dla: $x\in[-10,10]$ oraz $y\in[-10,10]$

funkcja $F_{Eas}$ w danym przedziale osiąga maksymalną wartość dla:
$max(F_{Eas}) = F_{Eas}(\pi,\pi) = 1$

Wzór funkcji $F_{Eas}$ przedstawia wykres \ref{fig:test_function_easom}.

      \begin{figure}[!ht]
	\includegraphics[width=16cm]{../test_function_easom}
	\caption{Wykres funkcji $F_{Eas}$ określonej wzorem \ref{eq:test_function_easom}}
	\label{fig:test_function_easom}
      \end{figure}

Pomimo prostego wykresu funkcja ta okazała się niezwykle trudna dla algorytmu genetycznego. Selekcja turniejowa z rozmiarem turnieju $ts=10$ działała bardzo nieefektywnie i w niektórych przypadkach nie potrafiła znaleźć rozwiązania nawet w 30000 generacji. Ze względu na złe działanie selekcji turniejowej dla funkcji Easom'a zastosowano selekcje deterministyczną. Po uruchomieniu algorytmu 100 razy algorytm znalazł rozwiązanie średnio w \glslink{generacja}{generacji} 548.68 a odchylenie wyniosło 859.139, co jest wartością dużą w porównaniu z poprzednimi funkcjami. W najgorszym ze 100 uruchomień rozwiązanie znaleziono w 3698 generacji.

Przy poszukiwaniu maksimum funkcji Easom'a tworzonych jest wiele chromosomów o bardzo podobnym przystosowaniu. Niezwykle trudno jest trafić na obszar otaczający dobre rozwiązanie, ponieważ jest on wąski i nie istnieją rozwiązania pośrednie prowadzące do tego obszaru. Selekcja turniejowa działała słabo, ponieważ nawet jeśli znaleziono \gls{chromosom} o lepszym przystosowaniu niż cała \gls{populacja} niekoniecznie musiał on wejść w skład nowego pokolenia lub mógł uzyskać małą liczbę kopii. Selekcja deterministyczna sprawdziła się dużo lepiej, ponieważ kiedy tylko pojawił się osobnik lepszy od reszty automatycznie zyskiwał dużą liczbę potomków. W przypadku tej funkcji, gdzie brak jest \glslink{pulapkaewolucyjna}{pułapek ewolucyjnych} \gls{zbieznosc} do pierwszego napotkanego osobnika lepszego od reszty (super-osobnika) jest pożądana. Po uruchomieniu algorytmu z selekcją deterministyczną na 5000 \glslink{generacja}{generacji} uzyskano wynik:

%172247|172248
%3.1414533289082675616|3.1415296231446196984
%fitness: 0.99999996492369480627

      \begin{center}
      $x = 3.1414533289082675616$\\
      $y = 3.1415296231446196984$\\
      $F_{Eas}(x,y) = 0.99999996492369480627$\\
      \end{center}

\section{Problemy NP-zupełne}
\label{sec:np_complete_problems}
Cechą problemów NP-zupełnych jest to, że aby znaleźć rozwiązanie optymalne trzeba przeszukać całą pulę możliwych rozwiązań.
Czas potrzebny na znalezienie rozwiązania problemu NP-zupełnego wzrasta bardzo szybko w miarę zwiększenia rozmiaru problemu.
  Przykłady problemów NP-zupełnych:
  \begin{itemize}
  \item Kolorowanie grafu
  \item Problem komiwojażera
  \item Problem plecakowy
  %\item Tetris
  %\item Saper
  \item Sudoku
  \end{itemize}

W kolejnych rozdziałach zostaną omówione wybrane problemy NP-zupełne.

\subsection{Problem komiwojażera}
\label{sec:salesman}
Problem podróżującego komiwojażera polega na znalezieniu najkrótszej drogi pomiędzy zadanymi miastami. Trasa musi przechodzić przez wszystkie miasta dokładnie raz i kończyć się w miejscu startu. Znane są odległości pomiędzy wszystkimi miastami.
Dalsze rozważania dotyczą problemu symetrycznego, to znaczy odległość z miast A do B jest równa odległości z miasta B do A.

Liczba możliwych dróg równa jest liczbie permutacji podzielonej przez 2 (trasę można przebyć w dwóch kierunkach).
Dla liczby miast $n_m=20$ ilość możliwych dróg wynosi $\frac{(n_m-1)!}{2}=\frac{19!}{2}=60822550204416000$

\subsubsection{Wybór odpowiedniego kodowania w chromosomie}
\label{sec:salesman_chromosome}
  Istnieje wiele możliwości \glslink{reprezentacja}{reprezentacji} problemu komiwojażera w chromosomie. W niniejszej pracy użyto \glslink{reprezentacja}{reprezentacji} ścieżkowej \cite{michalewicz}, która zawiera kolejność odwiedzanych miast.
  Chromosom dla problemu komiwojażera jest szczególnym przypadkiem chromosomu zawierającego ciąg liczb całkowitych od $0$ do $l-1$, gdzie $l$ jest długością chromosomu. Różnica polega na tym, że wystąpić muszą wszystkie liczby od $0$ do $l-1$ dokładnie raz. Chromosom zawierał więc będzie permutację liczb od $0$ do $l-1$. Chromosom z tabeli \ref{tb:example_chromosome_salesman} przedstawia trasę dla 9 miast ponumerowanych od 0 do 8 w kolejności: \\
  $1 \rightarrow 5 \rightarrow 8 \rightarrow 3 \rightarrow 0 \rightarrow 2 \rightarrow 6 \rightarrow 4 \rightarrow 7 \rightarrow 1$

  \begin{table}[!ht]
    \caption{Przykładowy chromosom dla problemu komiwojażera}
    \label{tb:example_chromosome_salesman}
    \begin{center}
	\begin{tabular}{ | l | l |l |l |l |l |l |l |l |}
	\hline
	1&5&8&3&0&2&6&4&7\\ \hline
	\end{tabular}
    \end{center}
  \end{table}

\paragraph{Krzyżowanie}
  Zwykłe krzyżowanie polegające na wymianie części chromosomów prowadziłoby do utworzenia nieprawidłowych chromosomów z powtarzającymi się liczbami. Należy zastosować wyspecjalizowane krzyżowanie, które tworzy tylko prawidłowe chromosomy.

W tym celu po wybraniu punktu krzyżowania sprawdzamy kolejne pozycje do zamiany. Tabela \ref{tb:example_crossover_salesman} prezentuje kolejne kroki krzyżowania dla chromosomów o długości $l=9$ i punktu krzyżowania 5. W chromosomie A znajdujemy pozycję, na której znajduje się liczba z pozycji 6 chromosomu B (liczba 8). Następnie liczba ze znalezionej pozycji zostaje zamieniona z liczbą na pozycji 6. Tak samo postępujemy z chromosomem B. Czynność powtarzamy dla wszystkich pozycji znajdujących się za punktem krzyżowania.

  \begin{table}[!ht]
    \caption{Przykład procesu krzyżowania dla problemu komiwojażera}
    \label{tb:example_crossover_salesman}
    \begin{center}
	\begin{tabular}{ | l | l | l|}
	\hline
	chromosom A & chromosom B\\ \hline
	1 5 8 3 0|2 6 4 7 & 3 5 1 6 0|8 7 2 4\\ \hline
	1 5 {\color{red}2} 3 0|{\color{red}8} 6 4 7 & 3 5 1 6 0|{\color{red}2} 7 {\color{red}8} 4\\ \hline
	1 5 2 3 0|8 {\color{red}7} 4 {\color{red}6} & 3 5 1 {\color{red}7} 0|2 {\color{red}6} 8 4\\ \hline
	1 5 {\color{red}4} 3 0|8 7 {\color{red}2} 6 & 3 5 1 7 0|2 6 {\color{red}4} {\color{red}8}\\ \hline
	1 5 {\color{red}6} 3 0|8 7 2 {\color{red}4} & 3 5 1 {\color{red}8} 0|2 6 4 {\color{red}7}\\ \hline
	\end{tabular}
    \end{center}
  \end{table}

\paragraph{Mutacja}
  Ponieważ zmiana losowej pozycji spowodowałaby utworzenie chromosomu nieprawidłowego to mutacja w przypadku problemu komiwojażera polega na zamianie miejscami dwóch losowych miast. Tabela \ref{tb:example_mutation_salesman} zawiera przykład mutacji.

  \begin{table}
    \caption{Przykład mutacji dla problemu komiwojażera}
    \label{tb:example_mutation_salesman}
    \begin{center}
	\begin{tabular}{|l | l | l |l |l |l |l |l |l |l |}
	\hline
	przed mutacją &1&5&8&3&0&2&6&4&7\\ \hline
	po mutacji    &1&5&{\color{red}2}&3&0&{\color{red}8}&6&4&7\\ \hline
	\end{tabular}
    \end{center}
  \end{table}

\subsubsection{Opis aplikacji}

Aby wykorzystać wcześniej opisaną bibliotekę obliczeń za pomocą algorytmów genetycznych do problemu komiwojażera należało napisać kilka klas specyficznych dla tego problemu (diagram klas na rysunku \ref{fig:class_diagram_salesman}).
\paragraph{SalesmanChromosome}
Klasa SalesmanChromosome implementuje interfejs klasy bazowej Chromosome definiując krzyżowanie i mutację jak opisano w rozdziale \ref{sec:salesman_chromosome}, posiada odpowiednie konstruktory, metodę do wypełnienia losowymi wartościami, która tworzy tylko prawidłowe chromosomy zawierające każde miasto dokładnie raz. Zaimplementowana jest także metoda {\tt duplicate()} tworząca kopię chromosomu.
Klasa SalesmanChromosome dziedziczy po IntegerChromosome, ponieważ część funkcji jest w tych klasach identyczna i nie ma potrzeby ich ponownego definiowania.

\paragraph{SalesmanEnvironment}
Klasa SalesmanEnvironment przechowuje listę obiektów typu SalesmanChromosome a do ich tworzenia wykorzystuje SalesmanChromosomeFactory. SalesmanEnvironment dziedziczy po AbstractEnvironment i implementuje metody takie jak {\tt fitnessFunction()}, która oblicza długość trasy dla chromosomu na podstawie danych zawartych w  obiekt klasy SalesmanData (przekazywany jako parametr konstruktora). Metoda {\tt decodeChromosome()} pozwala zdekodować informację zawartą w chromosomie. Jest też możliwość obliczenia najlepszej trasy algorytmem brute-force, służy do tego metoda findBestSalesmanRoute(), która oblicza długość trasy dla wszystkich permutacji miast tworzonych metodą {\tt getNextPermutation()}. Szukanie rozwiązania metodą brute-force jest jednak bardzo mało efektywne.

\paragraph{SalesmanData}
Klasa SalesmanData służy do przechowywania listy miast wraz z odległościami pomiędzy nimi. Miasta są przechowywane jako obiekty klasy SalesmanCity. Do dodawania kolejnych miast służy metoda {\tt addCity()}, która podczas dodawania miasta aktualizuje tablicę odległości. Tablica odległości jest dwuwymiarowa (przykład w tabeli \ref{tb:example_distance_table_salesman}).

  \begin{table}
    \caption{Przykład tablicy odległości dla problemu komiwojażera}
    \label{tb:example_distance_table_salesman}
    \begin{center}
	\begin{tabular}{|l | l | l |l |l |}
	\hline
		&miasto 1&miasto 2&miasto 3&miasto 4\\ \hline
	miasto 1 &0	&156	&211	&63\\ \hline
	miasto 2	&156	&0	&22	&120\\ \hline
	miasto 3 &211	&22	&0	&71\\ \hline
	miasto 4 &63	&120	&71	&0\\ \hline
	\end{tabular}
    \end{center}
  \end{table}

Tablica jest wykorzystywana do obliczania długości trasy. Klasa SalesmanData posiada też metody umożliwiające zapis i wczytywanie z pliku w formacie XML.

\paragraph{SalesmanCity}
Klasa ta zawiera nazwę i współrzędne jednego miasta.

\paragraph{Interfejs graficzny}
Graficzny interfejs użytkownika zapewniają klasy SalesmanCanvas oraz SalesmanMainWindow (rysunek \ref{fig:salesman_ui}). Klasa SalesmanCanvas pozwala na dodawanie miast przez użytkownika za pomocą myszki oraz prezentuje wyniki symulacji na mapie. Dane przechowywane są w obiekcie klasy SalesmanData, który łatwo może być przekazywany do SalesmanEnvironment. Klasa SalesmanMainWindow zapewnia połączenie pomiędzy SalesmanEnvironment i SalesmanCanvas. Informuje ona SalesmanCanvas kiedy należy odświeżyć widok trasy oraz SalesmanEnvironment kiedy rozpocząć symulację. Pozwala także na ustawienie wszystkich parametrów symulacji i przekazuje te parametry do SalesmanEnvironment.

%TODO diagram klas salesman polaczenia canvas do main, klasa factory, dodac klase chromosome
\begin{figure}[!ht]
  \includegraphics[width=16cm]{../class_diagram_salesman}
  \caption{Diagram klas aplikacji rozwiązującej problem komiwojażera}
  \label{fig:class_diagram_salesman}
\end{figure}

\begin{figure}[!ht]
  \centering
  \includegraphics[width=14cm]{../salesman_ui}
  \caption{Widok interfejsu graficznego aplikacji}
  \label{fig:salesman_ui}
\end{figure}

\subsubsection{Proste zadanie - 16 miast}
W celu przetestowania algorytmu genetycznego rozwiązującego problem komiwojażera rozważono układ miast jak na rysunku \ref{ex:salesman_map1}.

\setlength{\unitlength}{1mm}

\begin{figure}[!ht]

\begin{picture}(65, 65) (-50,0)
  \put(0,20){\circle*{2}}
  \put(0,30){\circle*{2}}
  \put(0,40){\circle*{2}}
  \put(10,50){\circle*{2}}
  \put(20,60){\circle*{2}}
  \put(30,60){\circle*{2}}
  \put(40,60){\circle*{2}}
  \put(50,50){\circle*{2}}
  \put(60,40){\circle*{2}}
  \put(60,30){\circle*{2}}
  \put(60,20){\circle*{2}}
  \put(50,10){\circle*{2}}
  \put(40,0){\circle*{2}}
  \put(30,0){\circle*{2}}
  \put(20,0){\circle*{2}}
  \put(10,10){\circle*{2}}

  \put(1,21){$A$}
  \put(1,31){$B$}
  \put(1,41){$C$}
  \put(11,51){$D$}
  \put(21,61){$E$}
  \put(31,61){$F$}
  \put(41,61){$G$}
  \put(51,51){$H$}
  \put(61,41){$I$}
  \put(61,31){$J$}
  \put(61,21){$K$}
  \put(51,11){$L$}
  \put(41,1){$M$}
  \put(31,1){$N$}
  \put(21,1){$O$}
  \put(11,11){$P$}

\multiput(0,0)(10,0){7}%
  {\line(0,1){60}}

\multiput(0,0)(0,10){7}%
  {\line(1,0){60}}

\end{picture}
\caption{Mapa miast prostego problemu komiwojażera}
\label{ex:salesman_map1}
\end{figure}

Znalezienie najkrótszej drogi dla miast jak na rysunku \ref{ex:salesman_map1} nie jest trudne. Zaczynając od dowolnego miasta poruszamy się po ośmiokącie, na którego bokach leżą miasta. Optymalne rozwiązanie wynosi:

  \begin{equation}
  8 + 8\sqrt{8} \approx 19.313708
  \end{equation}

Liczba wszystkich możliwych dróg wynosi: $\frac{(n_m-1)!}{2}=\frac{15!}{2}=1307674368000$

Możemy przystąpić do analizy najlepszych parametrów środowiska ustawiając jako warunek zakończenia poszukiwania znalezienie rozwiązania optymalnego.
W tym celu uruchomiono algorytm z następującymi parametrami środowiska: prawdopodobieństwo krzyżowania $0.9$, prawdopodobieństwo mutacji $0.05$, selekcja turniejowa z rozmiarem turnieju $ts=10$, liczebność populacji $n = 100$. Warunkiem zakończenia było znalezienie trasy krótszej niż $19.313709$. Zastosowano także dodatkowe modyfikacje klasycznego algorytmu genetycznego: Dodawanie 4 nowych chromosomów w każdej generacji, dodawanie najlepszego dotychczas znalezionego rozwiązania do każdej generacji oraz zastępowanie duplikatów.
Algorytm uruchomiono 100 razy. Rozwiązanie zostało znalezione średnio w generacji 42.03 a odchylenie standardowe wyniosło 37.3145. W najgorszym przypadku rozwiązanie znaleziono w pokoleniu 224. 

Średnio algorytm sprawdzał $42.03 \cdot n = 42.03 \cdot 100 = 4203$ dróg a w najgorszym przypadku sprawdził $224 \cdot n = 224 \cdot 100 = 22400$ dróg.
Ponieważ znana jest całkowita liczba możliwych dróg łatwo obliczyć, że algorytm sprawdzał średnio $\frac{4203}{1307674368000}\cdot100\% = 0,000000323\%$ a w najgorszym przypadku $\frac{22400}{1307674368000}\cdot100\% =0,000001713\%$. Nawet w najgorszym przypadku jest to więc ilość niewielka. Pomimo sprawdzenia tak małej ilości rozwiązań algorytm był zbieżny i znalazł rozwiązanie optymalne.

\subsubsection{Problem komiwojażera dla 52 miast}

W tym rozdziale przeanalizowano działanie algorytmu dla mapy 52 miast jak na rysunku \ref{fig:salesman_map_50}. Liczba możliwych dróg dla 52 miast wynosi: $\frac{(n_m-1)!}{2}=\frac{51!}{2}=7,755593766e+65$.


%plik greedy+ga7.xml
\begin{figure}
  \centering
  \begin{tikzpicture}[scale=2]
%TODO rotate vertically?
\fill(1.38,1.08) circle (1pt);
\fill(1.05,1.58) circle (1pt);
\fill(2.26,2.17) circle (1pt);
\fill(3.36,1.19) circle (1pt);
\fill(3.21,2.55) circle (1pt);
\fill(3.33,3.52) circle (1pt);
\fill(.96,3.34) circle (1pt);
\fill(1.60,2.48) circle (1pt);
\fill(2.61,1.22) circle (1pt);
\fill(.82,.71) circle (1pt);
\fill(3.67,.42) circle (1pt);
\fill(4.09,1.90) circle (1pt);
\fill(4.07,3.07) circle (1pt);
\fill(2.13,3.20) circle (1pt);
\fill(2.59,.47) circle (1pt);
\fill(2.89,1.67) circle (1pt);
\fill(.26,2.30) circle (1pt);
\fill(1.02,2.61) circle (1pt);
\fill(1.93,.40) circle (1pt);
\fill(1.98,1.53) circle (1pt);
\fill(.54,1.25) circle (1pt);
\fill(1.81,1.03) circle (1pt);
\fill(.71,.15) circle (1pt);
\fill(3.21,.38) circle (1pt);
\fill(3.19,1.82) circle (1pt);
\fill(4.12,.58) circle (1pt);
\fill(2.81,3.24) circle (1pt);
\fill(1.45,3.50) circle (1pt);
\fill(1.41,.71) circle (1pt);
\fill(.45,1.78) circle (1pt);
\fill(1.05,2.06) circle (1pt);
\fill(.48,3.40) circle (1pt);
\fill(3.51,2.98) circle (1pt);
\fill(2.68,2.03) circle (1pt);
\fill(3.43,1.03) circle (1pt);
\fill(3.01,.93) circle (1pt);
\fill(.99,3.09) circle (1pt);
\fill(1.84,3.03) circle (1pt);
\fill(1.87,.65) circle (1pt);
\fill(2.21,.67) circle (1pt);
\fill(3.40,.53) circle (1pt);
\fill(3.15,.64) circle (1pt);
\fill(.66,2.54) circle (1pt);
\fill(.33,3.27) circle (1pt);
\fill(3.51,3.56) circle (1pt);
\fill(4.00,3.51) circle (1pt);
\fill(4.32,1.68) circle (1pt);
\fill(3.74,1.55) circle (1pt);
\fill(3.52,2.70) circle (1pt);
\fill(4.00,2.72) circle (1pt);
\fill(2.48,2.69) circle (1pt);
\fill(2.72,2.69) circle (1pt);

  \end{tikzpicture}
  \caption{Mapa 52 miast dla problemu komiwojażera}
  \label{fig:salesman_map_50}
\end{figure}


Ze względu na bardzo dużą liczbę możliwych dróg algorytm genetyczny potrzebuje zdecydowanie więcej czasu na znalezienie obszarów dobrych rozwiązań. W celu szybszej zbieżności algorytmu można zastosować prostą modyfikację, która znacznie usprawnia cały proces. Zamiast losować populację początkową można utworzyć ją wykorzystując inną metodę rozwiązywania problemu komiwojażera.

\paragraph{Algorytm zachłanny dla problemu komiwojażera}

Algorytm zachłanny \cite{algorytmy} to taki, który w każdym kroku wybiera rozwiązanie najlepsze lokalnie. Algorytm taki dla niektórych problemów może znajdować rozwiązanie optymalne globalnie, jednak nie dotyczy to problemu komiwojażera.

Jednym z najprostszych sposobów rozwiązywania problemu komiwojażera jest użycie algorytmu najbliższego sąsiada. Jest to algorytm zachłanny, który startuje z jednego z miast i w każdym kroku wybiera miasto najbliższe aktualnego, które nie zostało jeszcze odwiedzone. Następnie przechodzi do tego miasta i powtarza takie działanie, dopóki wszystkie miasta nie zostaną odwiedzone. Algorytm ten nie gwarantuje znalezienia rozwiązania optymalnego, jednak może posłużyć do utworzenia populacji początkowej dla algorytmu genetycznego. Takie postępowanie pozwala połączyć zalety dwóch zupełnie odmiennych metod i poprawić ich wyniki. Algorytm zachłanny znajduje rozwiązania dobre a algorytm genetyczny poprawia je dążąc do rozwiązania optymalnego. Algorytm genetyczny nie musi zaczynać poszukiwania od zupełnie losowych rozwiązań populacji początkowej dzięki czemu może działać krócej.

Długość najkrótszej znalezionej przez algorytm zachłanny drogi dla mapy miast jak na rysunku \ref{fig:salesman_map_50} wyniosła $2874.712$.

\paragraph{Standardowy algorytm genetyczny}
Algorytm genetyczny uruchomiono 100 razy z następującymi parametrami środowiska: prawdopodobieństwo krzyżowania $0.9$, prawdopodobieństwo mutacji $0.05$, selekcja turniejowa z rozmiarem turnieju $ts=20$, liczebność populacji $n = 1000$. Warunkiem zakończenia było osiągnięcie 500 generacji. Zastosowano także dodatkowe modyfikacje klasycznego algorytmu genetycznego: Dodawanie 4 nowych chromosomów w każdej generacji, dodawanie najlepszego dotychczas znalezionego rozwiązania do każdej generacji oraz zastępowanie duplikatów.

Średnio długość najkrótszej znalezionej drogi wyniosła $3180.83$ a odchylenie od tej średniej wyniosło $198.335$.
Znaleziona przez algorytm genetyczny najkrótsza droga była więc średnio gorsza niż ta, znaleziona przez prosty algorytm zachłanny. W takim przypadku należałoby zwiększyć liczbę pokoleń generowanych przez algorytm co jednak skutkowałoby dłuższym działaniem. Lepszym rozwiązaniem jest utworzenie populacji początkowej o większej wartości przystosowania z wykorzystaniem algorytmu zachłannego. 

\paragraph{Połączenie algorytmu genetycznego z algorytmem zachłannym}
Algorytm genetyczny uruchomiono ponownie z identycznymi parametrami, jednak do utworzenia populacji początkowej użyto algorytmu zachłannego, który startował z różnych miast.
Po 100 uruchomieniach zmodyfikowanego algorytmu średnio najkrótsza znaleziona droga miała długość $2673.13$ a odchylenie standardowe wyniosło $15.5432$.

Połączenie algorytmu zachłannego i genetycznego przyniosło dobre rezultaty. Populacja początkowa zawierająca chromosomy o dużym przystosowaniu, w porównaniu do chromosomów losowych, pozwoliła ukierunkować proces w dobrym kierunku. Algorytm genetyczny poprawiał rozwiązanie znalezione przez algorytm zachłanny a wyniki były znacznie lepsze niż w przypadku standardowego algorytmu genetycznego. Także odchylenie standardowe było dużo mniejsze co świadczy, że proces był bardziej ustabilizowany. Do rozwiązywania problemu komiwojażera o dużej ilości miast warto więc zastosować połączenia dwóch typów algorytmów.

\begin{figure}[!ht]
  \centering
  \includegraphics[width=16cm]{../salesman_52_greedy_ga}
  \caption{Porównanie zbieżności algorytmu standardowego i połączonego z zachłannym}
  \label{fig:salesman_52_greedy_ga}
\end{figure}

Rysunek \ref{fig:salesman_52_greedy_ga} przedstawia wykres zbieżności jednego uruchomienia algorytmu genetycznego z populacją początkową wylosowaną oraz utworzoną za pomocą algorytmu zachłannego. Na wykresie oznaczona jest także wartość znaleziona przez algorytm zachłanny, która jest właściwie punktem startowym algorytmu genetycznego. Dla klasycznego algorytmu genetycznego widać szybką zbieżność w początkowej fazie symulacji, gdzie często znajdowane są lepsze rozwiązania. Zbieżność zwalnia jednak stopniowo na poziomie wartości około 3500 i w dalszej części symulacji jest wolniejsza nie osiągając poziomu rozwiązania znalezionego przez algorytm zachłanny. Algorytm genetyczny z populacją początkową utworzoną algorytmem zachłannym startuje z poziomu dużo lepszych rozwiązań niż algorytm standardowy i systematycznie poprawia rozwiązanie w kolejnych pokoleniach uzyskując dużo lepszy wynik. Około pokolenia 250 tempo zbieżności obu algorytmów wyrównuje się, ale wersja z algorytmem zachłannym przetwarza populację o wartości przystosowania średnio lepszej o około 500. Najlepsza trasa znaleziona w jednym z uruchomień jest przedstawiona na rysunku \ref{fig:salesman_52_greedy_ga_best}.

%\begin{figure}[!ht]
%  \centering
%  \includegraphics[width=7cm]{../salesman_52_greedy_ga_best.png}
%  \caption{Najlepsza znaleziona trasa}
%  \label{fig:salesman_52_greedy_ga_best}
%\end{figure}


\begin{figure}
  \centering
  \begin{tikzpicture}[scale=2]
%TODO rotate vertically?
\fill(1.38,1.08) circle (1pt);
\fill(1.05,1.58) circle (1pt);
\fill(2.26,2.17) circle (1pt);
\fill(3.36,1.19) circle (1pt);
\fill(3.21,2.55) circle (1pt);
\fill(3.33,3.52) circle (1pt);
\fill(.96,3.34) circle (1pt);
\fill(1.60,2.48) circle (1pt);
\fill(2.61,1.22) circle (1pt);
\fill(.82,.71) circle (1pt);
\fill(3.67,.42) circle (1pt);
\fill(4.09,1.90) circle (1pt);
\fill(4.07,3.07) circle (1pt);
\fill(2.13,3.20) circle (1pt);
\fill(2.59,.47) circle (1pt);
\fill(2.89,1.67) circle (1pt);
\fill(.26,2.30) circle (1pt);
\fill(1.02,2.61) circle (1pt);
\fill(1.93,.40) circle (1pt);
\fill(1.98,1.53) circle (1pt);
\fill(.54,1.25) circle (1pt);
\fill(1.81,1.03) circle (1pt);
\fill(.71,.15) circle (1pt);
\fill(3.21,.38) circle (1pt);
\fill(3.19,1.82) circle (1pt);
\fill(4.12,.58) circle (1pt);
\fill(2.81,3.24) circle (1pt);
\fill(1.45,3.50) circle (1pt);
\fill(1.41,.71) circle (1pt);
\fill(.45,1.78) circle (1pt);
\fill(1.05,2.06) circle (1pt);
\fill(.48,3.40) circle (1pt);
\fill(3.51,2.98) circle (1pt);
\fill(2.68,2.03) circle (1pt);
\fill(3.43,1.03) circle (1pt);
\fill(3.01,.93) circle (1pt);
\fill(.99,3.09) circle (1pt);
\fill(1.84,3.03) circle (1pt);
\fill(1.87,.65) circle (1pt);
\fill(2.21,.67) circle (1pt);
\fill(3.40,.53) circle (1pt);
\fill(3.15,.64) circle (1pt);
\fill(.66,2.54) circle (1pt);
\fill(.33,3.27) circle (1pt);
\fill(3.51,3.56) circle (1pt);
\fill(4.00,3.51) circle (1pt);
\fill(4.32,1.68) circle (1pt);
\fill(3.74,1.55) circle (1pt);
\fill(3.52,2.70) circle (1pt);
\fill(4.00,2.72) circle (1pt);
\fill(2.48,2.69) circle (1pt);
\fill(2.72,2.69) circle (1pt);

   \draw[thick] 
(1.38,1.08) -- (1.81,1.03) -- (2.61,1.22) -- (1.98,1.53) -- (1.60,2.48) -- (1.05,2.06) -- (1.05,1.58) -- (.82,.71) -- (.71,.15) -- (.54,1.25) -- (.45,1.78) -- (.26,2.30) -- (.66,2.54) -- (1.02,2.61) -- (.99,3.09) -- (.33,3.27) -- (.48,3.40) -- (.96,3.34) -- (1.45,3.50) -- (1.84,3.03) -- (2.13,3.20) -- (2.48,2.69) -- (2.72,2.69) -- (3.21,2.55) -- (3.52,2.70) -- (3.51,2.98) -- (4.00,2.72) -- (4.07,3.07) -- (4.00,3.51) -- (3.51,3.56) -- (3.33,3.52) -- (2.81,3.24) -- (2.26,2.17) -- (2.68,2.03) -- (2.89,1.67) -- (3.19,1.82) -- (4.09,1.90) -- (4.32,1.68) -- (3.74,1.55) -- (3.36,1.19) -- (3.43,1.03) -- (3.01,.93) -- (3.15,.64) -- (3.40,.53) -- (4.12,.58) -- (3.67,.42) -- (3.21,.38) -- (2.59,.47) -- (2.21,.67) -- (1.93,.40) -- (1.87,.65) -- (1.41,.71) -- (1.38,1.08);

  \end{tikzpicture}
  \caption{Najlepsza znaleziona trasa}
  \label{fig:salesman_52_greedy_ga_best}
\end{figure}
%1 22 9 20 8 31 2 10 23 21 30 17 43 18 37 44 32 7 28 38 14 51 52 5 49 33 50 13 46 45 6 27 3 34 16 25 12 47 48 4 35 36 42 41 26 11 24 15 40 19 39 29


\subsection{Sudoku}
\label{sec:sudoku}
Sudoku to diagram wypełniony początkowo pewną ilością cyfr. Zwykle diagram ma rozmiar 9 x 9 i zawiera cyfry od 1 do 9. Rozwiązanie diagramu polega na takim wypełnieniu diagramu cyframi aby w każdym wierszu, każdej kolumnie oraz każdym kwadracie 3 x 3 cyfry z zakresu 1-9 pojawiły się dokładnie raz. Przykładowy diagram początkowy przedstawia rysunek \ref{fig:sudoku_example}.

\begin{table}[!ht]
  \caption{Przykładowy diagram sudoku}
  \label{fig:sudoku_example}
  \begin{center}
    \renewcommand{\arraystretch}{1.3}
    \begin{tabular}{!{\vrule width 2pt}c|c|c!{\vrule width 2pt}c|c|c%
    !{\vrule width 2pt}c|c|c!{\vrule width 2pt}}
      \noalign{\hrule height 2pt}
      2 &   &   & 6 &   & 7 & 5 &   &  \\ \hline
	&   &   &   &   &   &   & 9 & 6\\ \hline
      6 &   & 7 &   &   & 1 & 3 &   &  \\ \noalign{\hrule height 2pt}
	& 5 &   & 7 & 3 & 2 &   &   &  \\ \hline
	& 7 &   &   &   &   &   & 2 &  \\ \hline
	&   &   & 1 & 8 & 9 &   & 7 &  \\ \noalign{\hrule height 2pt}
	&   & 3 & 5 &   &   & 6 &   & 4\\ \hline
      8 & 4 &   &   &   &   &   &   &  \\ \hline
	&   & 5 & 2 &   & 6 &   &   & 8\\ \noalign{\hrule height 2pt}
    \end{tabular}
  \end{center}
\end{table}

W celu ułatwienia rozwiązywania zwykle tworzy się listę możliwych do wpisania cyfr dla każdego pola i w miarę wpisywania cyfr w diagram lista ulega skróceniu.

Część diagramów można rozwiązać na podstawie analizy wpisanych cyfr i eliminacji kolejnych możliwości, istnieją jednak trudne diagramy gdzie rozwiązanie wymaga kolejnego sprawdzania wszystkich możliwych do wpisania cyfr w każde pole.

\subsubsection{Wybór odpowiedniego kodowania w chromosomie}

Diagram sudoku zawiera liczby całkowite, więc naturalnym kodowaniem będzie chromosom o ciągu kodowym składającym się z liczb całkowitych. Podstawowy chromosom liczb całkowitych wymaga jednak kilku usprawnień. Na podstawie listy możliwych do wpisania cyfr w każde pole można ograniczyć liczbę chromosomów i uniknąć tworzenia błędnych rozwiązań. Dla każdej z cyfr ciągu kodowego utworzona zostaje lista możliwości i jest wykorzystywana przy losowym wypełnianiu chromosomu a także przy mutacji.

\paragraph{Krzyżowanie}
Ponieważ wszystkie utworzone początkowo chromosomy zawierają tylko możliwe do wpisania w każde pole cyfry, krzyżowanie nie wymaga modyfikacji. Po skrzyżowaniu dwóch prawidłowych chromosomów powstanie prawidłowy potomek.

\paragraph{Mutacja}
Mutacja w stosunku do zwykłego chromosomu liczb całkowitych różni się tym, że mutowana wartość jest zastępowana liczbą z listy możliwych do wpisania możliwości w daną komórkę a nie spośród wszystkich liczb z przedziału od minimum do maksimum.

\paragraph{Dodatkowy operator sudoku}
Charakterystyka problemu sudoku daje możliwości zastosowania dodatkowego operatora. Podczas działania algorytm genetyczny zwykle tworzy wiele chromosomów o przystosowaniu bliskiemu właściwemu rozwiązaniu. Często aby z chromosomu o dobrym przystosowaniu utworzyć rozwiązanie należy zamienić dwie komórki wartościami. Obserwacja działania klasycznego algorytmu skłoniła autora do napisania dodatkowego operatora.

Najpierw dla danej komórki tworzona jest lista komórek, dla których możliwa jest zamiana wartości z komórką bazową. Komórki te są wybierane tylko z wiersza/kolumny/kwadratu w którym znajduje się komórka bazowa. Następnie z utworzonej listy losowana jest jedna komórka i jej wartość jest zamieniana z komórką bazową. Jeśli komórki zawierają takie same wartości, to dla jednej z nich przeprowadzany jest operator mutacji.

Prawdopodobieństwo dla tego operatora określa możliwość wybrania jednej komórki jako komórki bazowej. Druga komórka jest wybierana losowo.
\subsubsection{Opis aplikacji}
Diagram klas napisanych w celu rozwiązywania sudoku przedstawia rysunek \ref{fig:class_diagram_sudoku}. Klasy zostały omówione poniżej.

\paragraph{SudokuCell}
Klasa SudokuCell definiuje jedną komórkę diagramu sudoku. Komórka zawiera wartość ({\tt value}) oraz informację czy jest to wartość pewna ({\tt prior}). Wektor bitowy possiblArr określa możliwe do wpisania w daną komórkę liczby tak, aby spełniały warunki poprawnego diagramu sudoku. Klasa posiada odpowiednie konstruktory oraz metody do ustawiania i pobierania wartości.

\paragraph{SudokuData}
SudokuData zawiera listę komórek typu SudokuCell a także rozmiar sudoku {\tt size} (zwykle 9) oraz rozmiar małego kwadratu {\tt sizeBox}, który jest równy $sizeBox = \sqrt{size}$. Wartości te są ustawiane w konstruktorze, który przyjmuje ciąg znaków zawierający cyfry rozdzielone dowolnym innym znakiem.

Konstruktor dzieli ciąg znaków na cyfry, ustala {\tt size} oraz {\tt sizeBox} i wpisuje wartości w komórki. Puste komórki są oznaczone zerem. Następnie jest wywoływana metoda {\tt excludeAllPossibl()} korzystająca z {\tt excludePossibl()}, która wypełnia wektory {\tt possiblArr} dla wszystkich komórek w diagramie. Metoda przechodzi kolejno wszystkie pola diagramu i wyklucza liczbę zawartą w aktualnej komórce z wiersza, kolumny i kwadratu, do którego ta komórka należy. Metoda {\tt countPossibleSolutions()} służy do policzenia wszystkich możliwych kombinacji liczb, które wynikają z wypełnionych wektorów {\tt possiblArr}.

\paragraph{SudokuChromosome}
SudokuChromosome dziedziczy po IntegerChromosome i dodatkowo zawiera listę {\tt cluesArr} z możliwymi do wpisania liczbami we wszystkie komórki. Przechowywanie tych danych w liście umożliwia łatwiejsze zaimplementowanie mutacji, dlatego nie zastosowano wektora liczb binarnych jak w przypadku SudokuData. Metoda {\tt getRandomValue()} losuje jedną z wartości znajdujących się na liście {\tt cluesArr} dla danego pola. SudokuChromosome przechowuje tylko tyle liczb, ile jest pustych miejsc w diagramie sudoku. 

\paragraph{SudokuEnvironment}
SudokuEnvironment przechowuje dane dotyczące rozwiązywanego diagramu w obiekcie typu SudokuData. Konstruktor przyjmuje obiekt klasy SudokuData i na podstawie danych w nim zawartych wypełnia {\tt cluesArr}, której wskaźnik jest później przekazywany do SudokuChromosomeFactory i dalej do wszystkich utworzonych chromosomów. W przypadku sudoku znana jest wartość najlepszego dopasowania więc konstruktor ustawia tą wartość. Wartość przystosowania liczona w funkcji {\tt fitnessFunction()} jest równa ilości unikatowych liczb w każdym wierszu, kolumnie i kwadracie. Funkcja {\tt countIndividuals()} jest odpowiedzialna za zliczanie tych unikatowych wartości. Najlepsze dopasowanie wynosi więc $max(f) = size^2 \cdot 3 = 243$. Warunkiem zakończenia poszukiwań dla sudoku będzie więc znalezienie chromosomu o wartości przystosowania równej 243. 

\begin{figure}[!ht]
  \includegraphics[width=16cm]{../class_diagram_sudoku}
  \caption{Diagram klas sudoku}
  \label{fig:class_diagram_sudoku}
\end{figure}

\subsubsection{Rozwiązanie prostego diagramu}
%7,9,0,0,0,0,3,0,0,
%0,0,0,0,0,6,9,0,0,
%8,0,0,0,3,0,0,7,6,
%0,0,0,0,0,5,0,0,2,
%0,0,5,4,1,8,7,0,0,
%4,0,0,7,0,0,0,0,0,
%6,1,0,0,9,0,0,0,8,
%0,0,2,3,0,0,0,0,0,
%0,0,9,0,0,0,0,5,4

W tym rozdziale przeanalizowano wyniki działania algorytmu dla diagramu sudoku jak w tabeli \ref{tb:sudoku_example2}.

\begin{table}[!ht]
  \caption{Diagram sudoku}
  \label{tb:sudoku_example2}
  \begin{center}
    \renewcommand{\arraystretch}{1.3}
    \begin{tabular}{!{\vrule width 2pt}c|c|c!{\vrule width 2pt}c|c|c%
    !{\vrule width 2pt}c|c|c!{\vrule width 2pt}}
      \noalign{\hrule height 2pt}
      7 & 9 &   &   &   &   & 3 &   &  \\ \hline
	&   &   &   &   & 6 & 9 &   &  \\ \hline
      8 &   &   &   & 3 &   &   & 7 & 6\\ \noalign{\hrule height 2pt}
	&   &   &   &   & 5 &   &   & 2\\ \hline
	&   & 5 & 4 & 1 & 8 & 7 &   &  \\ \hline
      4 &   &   & 7 &   &   &   &   &  \\ \noalign{\hrule height 2pt}
      6 & 1 &   &   & 9 &   &   &   & 8\\ \hline
	&   & 2 & 3 &   &   &   &   &  \\ \hline
	&   & 9 &   &   &   &   & 5 & 4\\ \noalign{\hrule height 2pt}
    \end{tabular}
  \end{center}
\end{table}

Dla podanego diagramu wygenerowano tablicę cyfr możliwych do wpisania do każdej komórki. Tam, gdzie możliwość była tylko jedna cyfrę wstawiono jako pewną. Tabela \ref{tb:sudoku_example_clues} przedstawia przekształcony diagram z tabeli \ref{tb:sudoku_example2} wraz z wpisanymi możliwościami. Na podstawie ilości możliwych do wpisania cyfr w każdą komórkę można obliczyć liczbę wszystkich chromosomów, jakie można utworzyć :
$3\cdot3\cdot3\cdot3\cdot4\cdot2 \cdot 3\cdot3\cdot2\cdot4\cdot3\cdot2 \cdot 2\cdot2\cdot2\cdot4\cdot3 \cdot 3\cdot3\cdot2\cdot2 \cdot 2\cdot2\cdot3\cdot3\cdot3 \cdot 2\cdot2 \cdot 3\cdot3\cdot3\cdot2\cdot2\cdot3 \cdot 2\cdot4\cdot2\cdot3\cdot2 = 12999674453557248 = 1.299967445e+16$
%\begin{comment}

\begin{table}[!ht]
  \caption{Diagram sudoku z zaznaczonymi możliwościami}
  \label{tb:sudoku_example_clues}
  \begin{center}
    \renewcommand{\arraystretch}{1.3}
    %\setlength{\extrarowheight}{0.5cm}
    \begin{tabular}{!{\vrule width 2pt}@{}p{0.5cm}|@{}p{0.5cm}|@{}p{0.5cm}!{\vrule width 2pt}@{}p{0.5cm}|@{}p{0.5cm}|@{}p{0.5cm}%
    !{\vrule width 2pt}@{}p{0.5cm}|@{}p{0.5cm}|@{}p{0.5cm}!{\vrule width 2pt}}
      \noalign{\hrule height 2pt}
      \hspace{0.25cm}7 & \hspace{0.25cm}9 & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny1 & \tiny  & \tiny \\
	\tiny4 & \tiny  & \tiny6\\
	\tiny  & \tiny  & \tiny \\
      \end{tabular}
    \end{minipage} &      
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny1 & \tiny2 & \tiny \\
	\tiny  & \tiny  & \tiny \\
	\tiny  & \tiny8  & \tiny \\
      \end{tabular}
    \end{minipage} &      
      \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny  & \tiny   & \tiny \\
	\tiny4 & \tiny5  & \tiny \\
	\tiny  & \tiny8  & \tiny \\
      \end{tabular}
    \end{minipage} &  
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny1 & \tiny2  & \tiny \\
	\tiny4 & \tiny   & \tiny \\
	\tiny  & \tiny   & \tiny \\
      \end{tabular}
    \end{minipage} & \hspace{0.25cm}3 & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny1  & \tiny2   & \tiny \\
	\tiny4 & \tiny  & \tiny \\
	\tiny  & \tiny8  & \tiny \\
      \end{tabular}
    \end{minipage} &     
     \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny1  & \tiny   & \tiny \\
	\tiny & \tiny5  & \tiny \\
	\tiny  & \tiny  & \tiny \\
      \end{tabular}
    \end{minipage}\\ \hline
    \hspace{0.25cm}2 &
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny  & \tiny   & \tiny3 \\
	\tiny4 & \tiny5  & \tiny \\
	\tiny  & \tiny  & \tiny \\
      \end{tabular}
    \end{minipage}& 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny1  & \tiny   & \tiny3 \\
	\tiny4 & \tiny  & \tiny \\
	\tiny  & \tiny  & \tiny \\
      \end{tabular}
    \end{minipage} & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny1  & \tiny   & \tiny \\
	\tiny & \tiny  & \tiny \\
	\tiny  & \tiny8  & \tiny \\
      \end{tabular}
    \end{minipage} & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny  & \tiny   & \tiny \\
	\tiny4 & \tiny5  & \tiny \\
	\tiny7  & \tiny8  & \tiny \\
      \end{tabular}
    \end{minipage} &  \hspace{0.25cm}6 & \hspace{0.25cm}9 & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny1  & \tiny   & \tiny \\
	\tiny4 & \tiny  & \tiny \\
	\tiny  & \tiny8  & \tiny \\
      \end{tabular}
    \end{minipage} & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny1  & \tiny   & \tiny \\
	\tiny & \tiny5  & \tiny \\
	\tiny  & \tiny  & \tiny \\
      \end{tabular}
    \end{minipage} \\ \hline
      \hspace{0.25cm}8 &
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny  & \tiny   & \tiny \\
	\tiny4 & \tiny5  & \tiny \\
	\tiny  & \tiny  & \tiny \\
      \end{tabular}
    \end{minipage} & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny1  & \tiny   & \tiny \\
	\tiny4 & \tiny  & \tiny \\
	\tiny  & \tiny  & \tiny \\
      \end{tabular}
    \end{minipage} & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny1  & \tiny2   & \tiny \\
	\tiny & \tiny  & \tiny \\
	\tiny  & \tiny  & \tiny \\
      \end{tabular}
    \end{minipage} & \hspace{0.25cm}3 & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny1  & \tiny2   & \tiny \\
	\tiny4 & \tiny  & \tiny \\
	\tiny  & \tiny  & \tiny9 \\
      \end{tabular}
    \end{minipage} & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny1  & \tiny   & \tiny \\
	\tiny4 & \tiny5  & \tiny \\
	\tiny  & \tiny  & \tiny \\
      \end{tabular}
    \end{minipage} & \hspace{0.25cm}7 & \hspace{0.25cm}6\\ \noalign{\hrule height 2pt}
	\hspace{0.25cm}1& 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny  & \tiny   & \tiny3 \\
	\tiny & \tiny  & \tiny \\
	\tiny7  & \tiny8  & \tiny \\
      \end{tabular}
    \end{minipage} & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny  & \tiny   & \tiny3 \\
	\tiny & \tiny  & \tiny \\
	\tiny7  & \tiny8  & \tiny \\
      \end{tabular}
    \end{minipage} & \hspace{0.25cm}9 & \hspace{0.25cm}6 & \hspace{0.25cm}5 & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny  & \tiny   & \tiny \\
	\tiny4 & \tiny  & \tiny \\
	\tiny  & \tiny8  & \tiny \\
      \end{tabular}
    \end{minipage} & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny  & \tiny   & \tiny \\
	\tiny4 & \tiny  & \tiny \\
	\tiny  & \tiny8  & \tiny \\
      \end{tabular}
    \end{minipage} & 2\\ \hline
      \hspace{0.25cm}9 & \hspace{0.25cm}2 & \hspace{0.25cm}5 & \hspace{0.25cm}4 & \hspace{0.25cm}1 & \hspace{0.25cm}8 & \hspace{0.25cm}7 & \hspace{0.25cm}6 & \hspace{0.25cm}3 \\ \hline
      \hspace{0.25cm}4 & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny  & \tiny   & \tiny \\
	\tiny  & \tiny   & \tiny6 \\
	\tiny  & \tiny8  & \tiny \\
      \end{tabular}
    \end{minipage} & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny  & \tiny   & \tiny \\
	\tiny & \tiny  & \tiny6 \\
	\tiny  & \tiny8  & \tiny \\
      \end{tabular}
    \end{minipage} & \hspace{0.25cm}7 & \hspace{0.25cm}2 & \hspace{0.25cm}3 & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny1  & \tiny   & \tiny \\
	\tiny & \tiny5  & \tiny \\
	\tiny  & \tiny8  & \tiny \\
      \end{tabular}
    \end{minipage} & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny1  & \tiny   & \tiny \\
	\tiny  & \tiny   & \tiny \\
	\tiny  & \tiny8  & \tiny9 \\
      \end{tabular}
    \end{minipage} & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny1  & \tiny   & \tiny \\
	\tiny & \tiny5  & \tiny \\
	\tiny  & \tiny  & \tiny9 \\
      \end{tabular}
    \end{minipage}\\ \noalign{\hrule height 2pt}
      \hspace{0.25cm}6 & \hspace{0.25cm}1 & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny  & \tiny   & \tiny \\
	\tiny4 & \tiny  & \tiny \\
	\tiny7  & \tiny  & \tiny \\
      \end{tabular}
    \end{minipage} & \hspace{0.25cm}5 & \hspace{0.25cm}9 & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny  & \tiny   & \tiny \\
	\tiny4 & \tiny  & \tiny \\
	\tiny7  & \tiny  & \tiny \\
      \end{tabular}
    \end{minipage} & \hspace{0.25cm}2 & \hspace{0.25cm}3 & \hspace{0.25cm}8\\ \hline
	\hspace{0.25cm}5& 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny  & \tiny   & \tiny \\
	\tiny4 & \tiny  & \tiny \\
	\tiny7  & \tiny8  & \tiny \\
      \end{tabular}
    \end{minipage} & \hspace{0.25cm}2 & \hspace{0.25cm}3 & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny  & \tiny   & \tiny \\
	\tiny4 & \tiny  & \tiny \\
	\tiny7  & \tiny8  & \tiny \\
      \end{tabular}
    \end{minipage} & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny1  & \tiny   & \tiny \\
	\tiny4 & \tiny  & \tiny \\
	\tiny7  & \tiny  & \tiny \\
      \end{tabular}
    \end{minipage} & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny1  & \tiny   & \tiny \\
	\tiny & \tiny  & \tiny6 \\
	\tiny  & \tiny  & \tiny \\
      \end{tabular}
    \end{minipage} & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny1  & \tiny   & \tiny \\
	\tiny & \tiny  & \tiny \\
	\tiny  & \tiny  & \tiny9 \\
      \end{tabular}
    \end{minipage} &     \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny1  & \tiny   & \tiny \\
	\tiny & \tiny  & \tiny \\
	\tiny7  & \tiny  & \tiny9 \\
      \end{tabular}
    \end{minipage}\\ \hline
	\hspace{0.25cm}3& 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny  & \tiny   & \tiny \\
	\tiny & \tiny  & \tiny \\
	\tiny7  & \tiny8  & \tiny \\
      \end{tabular}
    \end{minipage} & \hspace{0.25cm}9 & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny1  & \tiny2   & \tiny \\
	\tiny & \tiny  & \tiny6 \\
	\tiny  & \tiny8  & \tiny \\
      \end{tabular}
    \end{minipage} & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny  & \tiny   & \tiny \\
	\tiny & \tiny  & \tiny \\
	\tiny7  & \tiny8  & \tiny \\
      \end{tabular}
    \end{minipage} & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny1  & \tiny2   & \tiny \\
	\tiny & \tiny  & \tiny \\
	\tiny7  & \tiny  & \tiny \\
      \end{tabular}
    \end{minipage} & 
    \begin{minipage}{0.5cm}
      \renewcommand{\arraystretch}{0.5}
      \begin{tabular}{@{}p{0.25cm}@{}@{}p{0.25cm}@{}@{}p{0.25cm}@{}}
        \tiny1  & \tiny   & \tiny \\
	\tiny & \tiny  & \tiny6 \\
	\tiny  & \tiny  & \tiny \\
      \end{tabular}
    \end{minipage} & \hspace{0.25cm}5 & \hspace{0.25cm}4\\ \noalign{\hrule height 2pt}
    \end{tabular}
  \end{center}
\end{table}

%\end{comment}

%[7()].[9()].[0(146)].[0(128)].[0(458)].[0(124)].[3()].[0(1248)].[0(15)].
%[2()].[0(345)].[0(134)].[0(18)].[0(4578)].[6()].[9()].[0(148)].[0(15)].
%[8()].[0(45)].[0(14)].[0(12)].[3()].[0(1249)].[0(145)].[7()].[6()].

%[1()].[0(378)].[0(378)].[9()].[6()].[5()].[0(48)].[0(48)].[2()].
%[9()].[2()].[5()].[4()].[1()].[8()].[7()].[6()].[3()].
%[4()].[0(68)].[0(68)].[7()].[2()].[3()].[0(158)].[0(189)].[0(159)].

%[6()].[1()].[0(47)].[5()].[9()].[0(47)].[2()].[3()].[8()].
%[5()].[0(478)].[2()].[3()].[0(478)].[0(147)].[0(16)].[0(19)].[0(179)].
%[3()].[0(78)].[9()].[0(1268)].[0(78)].[0(127)].[0(16)].[5()].[4()].


Algorytm uruchomiono z następującymi parametrami środowiska: prawdopodobieństwo krzyżowania $p_c = 0.5$, prawdopodobieństwo mutacji $p_m = 0.05$, selekcja turniejowa z rozmiarem turnieju $ts=10$, liczebność populacji $n = 300$. Warunkiem zakończenia było znalezienie rozwiązania optymalnego. Zastosowano także dodatkowy operator z prawdopodobieństwem $p_s=0.03$ oraz dodatkowe modyfikacje klasycznego algorytmu genetycznego: dodawanie 4 nowych chromosomów w każdej generacji, dodawanie najlepszego dotychczas znalezionego rozwiązania do każdej generacji oraz zastępowanie duplikatów.

Dla 100 uruchomień algorytm znajdował rozwiązanie średnio w pokoleniu $62.85$ a odchylenie standardowe od tej średniej wyniosło $68.9442$. W najgorszym przypadku rozwiązanie zostało znalezione w generacji 437. Rozwiązany diagram przedstawia tabela \ref{tb:sudoku_example2_solved}.

\begin{table}[!ht]
  \caption{Rozwiązany diagram sudoku}
  \label{tb:sudoku_example2_solved}
  \begin{center}
    \renewcommand{\arraystretch}{1.3}
    \begin{tabular}{!{\vrule width 2pt}c|c|c!{\vrule width 2pt}c|c|c%
    !{\vrule width 2pt}c|c|c!{\vrule width 2pt}}
      \noalign{\hrule height 2pt}
      7 & 9 & 6 & 8 & 5 & 4 & 3 & 2 & 1\\ \hline
      2 & 4 & 3 & 1 & 7 & 6 & 9 & 8 & 5\\ \hline
      8 & 5 & 1 & 2 & 3 & 9 & 4 & 7 & 6\\ \noalign{\hrule height 2pt}
      1 & 3 & 7 & 9 & 6 & 5 & 8 & 4 & 2\\ \hline
      9 & 2 & 5 & 4 & 1 & 8 & 7 & 6 & 3\\ \hline
      4 & 6 & 8 & 7 & 2 & 3 & 5 & 1 & 9\\ \noalign{\hrule height 2pt}
      6 & 1 & 4 & 5 & 9 & 7 & 2 & 3 & 8\\ \hline
      5 & 8 & 2 & 3 & 4 & 1 & 6 & 9 & 7\\ \hline
      3 & 7 & 9 & 6 & 8 & 2 & 1 & 5 & 4\\ \noalign{\hrule height 2pt}
    \end{tabular}
  \end{center}
\end{table}

%"6,8,5,4,2,1,4,3,1,7,8,5,5,1,2,9,4,3,7,8,4,6,8,5,1,9,4,7,8,4,1,6,9,7,7,6,8,2,1"  fitness:  "243"  length:  39 

%[7()].[9()].[6(146)].[8(128)].[5(458)].[4(124)].[3()].[2(1248)].[1(15)].
%[2()].[4(345)].[3(134)].[1(18)].[7(4578)].[6()].[9()].[8(148)].[5(15)].
%[8()].[5(45)].[1(14)].[2(12)].[3()].[9(1249)].[4(145)].[7()].[6()].
%[1()].[3(378)].[7(378)].[9()].[6()].[5()].[8(48)].[4(48)].[2()].
%[9()].[2()].[5()].[4()].[1()].[8()].[7()].[6()].[3()].
%[4()].[6(68)].[8(68)].[7()].[2()].[3()].[5(158)].[1(189)].[9(159)].
%[6()].[1()].[4(47)].[5()].[9()].[7(47)].[2()].[3()].[8()].
%[5()].[8(478)].[2()].[3()].[4(478)].[1(147)].[6(16)].[9(19)].[7(179)].
%[3()].[7(78)].[9()].[6(1268)].[8(78)].[2(127)].[1(16)].[5()].[4()].

Średnio algorytm sprawdzał $62.85 \cdot n = 62.85 \cdot 300 = 18855$ możliwych rozwiązań a w najgorszym przypadku sprawdził $237 \cdot n = 437 \cdot 300 = 131100$. W porównaniu do liczby wszystkich możliwych do utworzenia chromosomów $1.29997e+16$ nawet w najgorszym przypadku liczba przetwarzanych chromosomów jest zaledwie ułamkiem procenta. Świadczy to o skuteczności algorytmu i wyraźnej zbieżności do rozwiązania najlepszego.


\subsubsection{Rozwiązanie diagramu z dużą ilością możliwości}
% plik 1.sud
%000000000400020360000070120000000000905000001070038092000006000002045016807100003
Diagram jak w tabeli \ref{tb:sudoku_example3} jest trudniejszy do rozwiązania dla algorytmu genetycznego niż poprzedni, ponieważ liczba możliwych do utworzenia chromosomów wynosi $2.58838e+31$.

%[0(123567)].[0(1235689)].[0(13689)].[0(345689)].[0(15689)].[0(1349)].[0(45789)].[0(4578)].[0(45789)].
%[4()].[0(1589)].[0(189)].[0(589)].[2()].[0(19)].[3()].[6()].[0(5789)].
%[0(356)].[0(35689)].[0(3689)].[0(345689)].[7()].[0(349)].[1()].[2()].[0(4589)].
%[0(1236)].[0(123468)].[0(13468)].[0(245679)].[0(1569)].[0(12479)].[0(45678)].[0(34578)].[0(4578)].
%[9()].[0(23468)].[5()].[0(2467)].[0(6)].[0(247)].[0(4678)].[0(3478)].[1()].
%[0(16)].[7()].[0(146)].[0(456)].[3()].[8()].[0(456)].[9()].[2()].
%[0(135)].[0(13459)].[0(1349)].[0(23789)].[0(89)].[6()].[0(245789)].[0(4578)].[0(45789)].
%[0(3)].[0(39)].[2()].[0(3789)].[4()].[5()].[0(789)].[1()].[6()].
%[8()].[0(4569)].[7()].[1()].[0(9)].[0(29)].[0(2459)].[0(45)].[3()].

%"6*7*5*6*5*4*5*4*5*4*3*3*2*4*3*5*4*6*3*4*4*6*5*6*4*5*5*5*4*5*4*1*3*4*4*2*3*3*3*3*5*4*5*2*6*4*5*1*2*4*3*4*1*2*4*2*"  =  2.58838e+31 

\begin{table}[!ht]
  \caption{Trudny diagram sudoku}
  \label{tb:sudoku_example3}
  \begin{center}
    \renewcommand{\arraystretch}{1.3}
    \begin{tabular}{!{\vrule width 2pt}c|c|c!{\vrule width 2pt}c|c|c%
    !{\vrule width 2pt}c|c|c!{\vrule width 2pt}}
      \noalign{\hrule height 2pt}
	&   &   &   &   &   &   &   &     \\ \hline
      4 &   &   &   & 2 &   & 3 & 6 &     \\ \hline
	&   &   &   & 7 &   & 1 & 2 &     \\ \noalign{\hrule height 2pt}
	&   &   &   &   &   &   &   &     \\ \hline
      9 &   & 5 &   &   &   &   &   & 1   \\ \hline
	& 7 &   &   & 3 & 8 &   & 9 & 2   \\ \noalign{\hrule height 2pt}
	&   &   &   &   & 6 &   &   &     \\ \hline
	&   & 2 &   & 4 & 5 &   & 1 & 6   \\ \hline
      8 &   & 7 & 1 &   &   &   &   & 3   \\ \noalign{\hrule height 2pt}
    \end{tabular}
  \end{center}
\end{table}

 Dla takiej ilości możliwości algorytm był mniej skuteczny i znalezienie rozwiązania było czasochłonne (ponad $26000$ pokoleń). W celu poprawy działania, bazując na doświadczeniach z rozdziału dotyczącego problemu komiwojażera, zastosowano dodatkową metodę analityczną przed uruchomieniem algorytmu genetycznego. Metoda ta (tzw. ang. {\it Hidden Singles}) sprawdzała kolejno wszystkie wiersze, kolumny i kwadraty. Jeśli w wierszu/kolumnie/kwadracie istniała tylko jedna komórka, w którą można było wstawić cyfrę to została ona wstawiona. Operację powtarzano dla cyfr 1-9. Po uruchomieniu dodatkowej analitycznej metody uzyskano diagram jak w tabeli \ref{tb:sudoku_example4} z ilością możliwych rozwiązań równą $7.22204e+16$.

%po naked(tylko):

%[0(12567)].[0(123568)].[0(13689)].[0(45689)].[0(15)].[0(1349)].[0(4579)].[0(4578)].[0(45789)].
%[4()].[0(158)].[0(189)].[0(589)].[2()].[0(19)].[3()].[6()].[0(5789)].
%[0(56)].[0(3568)].[0(3689)].[0(45689)].[7()].[0(349)].[1()].[2()].[0(4589)].
%[0(126)].[0(123468)].[0(13468)].[0(2459)].[0(15)].[0(1479)].[0(4567)].[0(34578)].[0(4578)].
%[9()].[0(2348)].[5()].[0(24)].[6()].[0(47)].[0(47)].[0(3478)].[1()].
%[0(16)].[7()].[0(146)].[0(45)].[3()].[8()].[0(456)].[9()].[2()].
%[0(15)].[0(145)].[0(14)].[3()].[8()].[6()].[0(24579)].[0(457)].[0(4579)].
%[3()].[9()].[2()].[7()].[4()].[5()].[8()].[1()].[6()].
%[8()].[0(456)].[7()].[1()].[9()].[2()].[0(45)].[0(45)].[3()].
%"5*6*5*5*2*4*4*4*5*3*3*3*2*4*2*4*4*5*3*4*3*6*5*4*2*4*4*5*4*4*2*2*2*4*2*3*2*3*2*3*2*5*3*4*3*2*2*"  =  1.82602e+24 

%SudokuData::findNakedSingles count:  3 
%SudokuData::findNakedSingles count:  3 
%SudokuData::findNakedSingles count:  1 
%SudokuData::findNakedSingles count:  2 
%SudokuData::findNakedSingles count:  0 
%SudokuData::findHiddenSingles count:  5 
%SudokuData::findHiddenSingles count:  3 
%SudokuData::findHiddenSingles count:  2 
%SudokuData::findHiddenSingles count:  0 

%po naked and hidden singles:
%naked znalazlo:9, hidden: 10 

%[7(156)].[2(1358)].[0(1368)].[0(4568)].[0(15)].[0(134)].[9(45)].[0(458)].[0(458)].
%[4()].[0(158)].[0(189)].[0(589)].[2()].[0(19)].[3()].[6()].[7(58)].
%[0(56)].[0(358)].[0(3689)].[0(45689)].[7()].[0(349)].[1()].[2()].[0(458)].
%[2(16)].[0(1348)].[0(13468)].[0(459)].[0(15)].[0(1479)].[0(4567)].[0(3458)].[0(458)].
%[9()].[0(348)].[5()].[2(4)].[6()].[0(47)].[0(47)].[0(348)].[1()].
%[0(16)].[7()].[0(146)].[0(45)].[3()].[8()].[0(456)].[9()].[2()].
%[0(15)].[0(145)].[0(14)].[3()].[8()].[6()].[2(45)].[7(45)].[9(45)].
%[3()].[9()].[2()].[7()].[4()].[5()].[8()].[1()].[6()].
%[8()].[6(45)].[7()].[1()].[9()].[2()].[0(45)].[0(45)].[3()].
%"4*4*2*3*3*3*3*3*3*2*2*3*4*5*3*3*4*5*3*2*4*4*4*3*3*2*2*3*2*3*2*3*2*3*2*2*2*"  =  7.22204e+16 

\begin{table}[!ht]
  \caption{Diagram po zastosowaniu metody Hidden Singles}
  \label{tb:sudoku_example4}
  \begin{center}
    \renewcommand{\arraystretch}{1.3}
    \begin{tabular}{!{\vrule width 2pt}c|c|c!{\vrule width 2pt}c|c|c%
    !{\vrule width 2pt}c|c|c!{\vrule width 2pt}}
      \noalign{\hrule height 2pt}
      7 & 2 &   &   &   &   & 9 &   &     \\ \hline
      4 &   &   &   & 2 &   & 3 & 6 & 7   \\ \hline
	&   &   &   & 7 &   & 1 & 2 &     \\ \noalign{\hrule height 2pt}
      2 &   &   &   &   &   &   &   &     \\ \hline
      9 &   & 5 & 2 & 6 &   &   &   & 1   \\ \hline
	& 7 &   &   & 3 & 8 &   & 9 & 2   \\ \noalign{\hrule height 2pt}
	&   &   & 3 & 8 & 6 & 2 & 7 & 9   \\ \hline
      3 & 9 & 2 & 7 & 4 & 5 & 8 & 1 & 6   \\ \hline
      8 & 6 & 7 & 1 & 9 & 2 &   &   & 3   \\ \noalign{\hrule height 2pt}
    \end{tabular}
  \end{center}
\end{table}

Następnie uruchomiono algorytm genetyczny z parametrami środowiska: prawdopodobieństwo krzyżowania $p_c = 0.5$, prawdopodobieństwo mutacji $p_m = 0.05$, selekcja turniejowa z rozmiarem turnieju $ts=10$, liczebność populacji $n = 300$. Warunkiem zakończenia było znalezienie rozwiązania optymalnego. Zastosowano także dodatkowy operator z prawdopodobieństwem $p_s=0.03$ oraz dodatkowe modyfikacje klasycznego algorytmu genetycznego: dodawanie 4 nowych chromosomów w każdej generacji, dodawanie najlepszego dotychczas znalezionego rozwiązania do każdej generacji oraz zastępowanie duplikatów.

Dla 100 uruchomień algorytm znajdował rozwiązanie średnio w generacji $3061.24$ a odchylenie standardowe wyniosło $3626,16$. W najgorszym przypadku rozwiązanie znaleziono w pokoleniu $16043$.

Średnio algorytm sprawdzał $3061.24 \cdot n = 3061.24 \cdot 300 = 918372$ możliwych rozwiązań a w najgorszym przypadku sprawdził $16043 \cdot n = 16043 \cdot 300 = 4812900$, co w porównaniu do liczby wszystkich możliwych do utworzenia chromosomów $7.22204e+16$ jest wynikiem satysfakcjonującym. Rozwiązany diagram przedstawiony jest w tabeli \ref{tb:sudoku_example4_solved}.

\begin{table}[!ht]
  \caption{Rozwiązany diagram}
  \label{tb:sudoku_example4_solved}
  \begin{center}
    \renewcommand{\arraystretch}{1.3}
    \begin{tabular}{!{\vrule width 2pt}c|c|c!{\vrule width 2pt}c|c|c%
    !{\vrule width 2pt}c|c|c!{\vrule width 2pt}}
      \noalign{\hrule height 2pt}
      7 & 2 & 1 & 6 & 5 & 3 & 9 & 8 & 4   \\ \hline
      4 & 5 & 9 & 8 & 2 & 1 & 3 & 6 & 7   \\ \hline
      6 & 3 & 8 & 4 & 7 & 9 & 1 & 2 & 5   \\ \noalign{\hrule height 2pt}
      2 & 4 & 3 & 9 & 1 & 7 & 6 & 5 & 8   \\ \hline
      9 & 8 & 5 & 2 & 6 & 4 & 7 & 3 & 1   \\ \hline
      1 & 7 & 6 & 5 & 3 & 8 & 4 & 9 & 2   \\ \noalign{\hrule height 2pt}
      5 & 1 & 4 & 3 & 8 & 6 & 2 & 7 & 9   \\ \hline
      3 & 9 & 2 & 7 & 4 & 5 & 8 & 1 & 6   \\ \hline
      8 & 6 & 7 & 1 & 9 & 2 & 5 & 4 & 3   \\ \noalign{\hrule height 2pt}
    \end{tabular}
  \end{center}
\end{table}

%[7(156)].[2(1358)].[1(1368)].[6(4568)].[5(15)].[3(134)].[9(45)].[8(458)].[4(458)].
%[4()].[5(158)].[9(189)].[8(589)].[2()].[1(19)].[3()].[6()].[7(58)].
%[6(56)].[3(358)].[8(3689)].[4(45689)].[7()].[9(349)].[1()].[2()].[5(458)].
%[2(16)].[4(1348)].[3(13468)].[9(459)].[1(15)].[7(1479)].[6(4567)].[5(3458)].[8(458)].
%[9()].[8(348)].[5()].[2(4)].[6()].[4(47)].[7(47)].[3(348)].[1()].
%[1(16)].[7()].[6(146)].[5(45)].[3()].[8()].[4(456)].[9()].[2()].
%[5(15)].[1(145)].[4(14)].[3()].[8()].[6()].[2(45)].[7(45)].[9(45)].
%[3()].[9()].[2()].[7()].[4()].[5()].[8()].[1()].[6()].
%[8()].[6(45)].[7()].[1()].[9()].[2()].[5(45)].[4(45)].[3()].

\section{Podsumowanie}
\label{sec:conclusion}

\subsection{Wnioski}
Przeprowadzone symulacje pozwalają na sformułowanie kilku wniosków. Najważniejszym z nich jest fakt, że algorytmy genetyczne, pomimo pozornej losowości, mogą być z powodzeniem stosowane do rozwiązywania różnych problemów o dużej ilości potencjalnych rozwiązań. Zastosowana implementacja algorytmu genetycznego, wybór sposobu krzyżowania, mutacji oraz selekcji i tworzenia nowych pokoleń okazał się trafny i pozwolił stosować główną część biblioteki do pracy z różnymi zagadnieniami.

Spośród metod selekcji najlepszą okazała się selekcja turniejowa. W niektórych przypadkach selekcja deterministyczna także przynosiła dobre efekty. Uzyskana mała efektywność metody ruletki jest zgodna z literaturą \cite{dejong}.

Dobór odpowiednich parametrów dla algorytmu okazał się bardzo ważnym etapem projektowania. Ustalone parametry pozwoliły znacznie poprawić działanie algorytmu i poprawić jego stabilność. Można także zauważyć pewne podobieństwo do naturalnej ewolucji z której czerpią algorytmy genetyczne - np. mały współczynnik prawdopodobieństwa mutacji, która także w przyrodzie występuje rzadko jednak jej rola jest ważna.

Przykłady z optymalizacją funkcji dwóch zmiennych pozwoliły na sprawdzenie, jak algorytm radzi sobie w przypadku istnienia wielu rozwiązań \glslink{rozwiazaniesuboptymalne}{rozwiązań suboptymalnych}. Pomimo istnienia wielu \glslink{pulapkaewolucyjna}{pułapek ewolucyjnych} rozwiązanie optymalne było znajdowane w niewielkiej ilości generacji.

Dla problemów NP-zupełnych dobre wyniki uzyskano dla problemu komiwojażera. Algorytm był zbieżny i systematycznie poprawiał rozwiązanie w kolejnych pokoleniach. Szczególnie dobre wyniki uzyskano przy połączeniu z algorytmem zachłannym, który tworzył populację początkową. Takie rozwiązanie pozwoliło na ominięcie początkowego przetwarzania przez algorytm zupełnie losowych rozwiązań o bardzo małej wartości przystosowania. Algorytm mógł startować z lepszego poziomu (populacja początkowa o dużym średnim przystosowaniu) i poprawiać wstępnie znalezione rozwiązanie. Ten przykład pozwala stwierdzić, że najlepsze wyniki algorytmy genetyczne uzyskują w połączeniu z metodami deterministycznymi.

Rozwiązywanie sudoku okazało się mniej efektywne ze względu na specyfikę tego problemu - istnienie jednego rozwiązania optymalnego i częstym brakiem rozwiązań pośrednich prowadzących do optimum. Ważnym elementem algorytmu genetycznego dla sudoku był dodatkowo napisany operator genetyczny, uwzględniający strukturę tego problemu. Pozwala to wysnuć wniosek, że klasyczny algorytm można znacznie ulepszyć poprzez dodawanie różnych modyfikacji dla różnych problemów.
Algorytmy genetyczne w przypadku sudoku mogą być skutecznie stosowane zamiast metody ``brute force'' w przypadku, kiedy nie jest możliwe znalezienie rozwiązania technikami analitycznymi. Tak jak w przypadku problemu komiwojażera warto więc połączyć metody deterministyczne i ewolucyjne.

Obie przedstawione we wstępie tezy potwierdziły się. Teza \ref{teza1} została udowodniona w rozdziałach \ref{sec:library_description}, \ref{sec:optimization} oraz \ref{sec:np_complete_problems}. W rozdziale \ref{sec:library_description} był przedstawiony sposób implementacji umożliwiający rozwiązywanie różnych zagadnień. Praktyczne zastosowania biblioteki opisane były w rozdziałach \ref{sec:optimization} oraz \ref{sec:np_complete_problems}. Teza \ref{teza2} została udowodniona w rozdziale \ref{sec:np_complete_problems}, gdzie opisano zastosowanie biblioteki dla dwóch zagadnień NP-zupełnych: problemu komiwojażera oraz do rozwiązywania Sudoku.

Algorytmy genetyczne okazały się dobrym sposobem na ukierunkowanie losowego przeszukiwania przestrzeni rozwiązań. Potwierdziło się założenie, że można je stosować dla wielu różnorodnych zagadnień. Analizowane problemu pozwalają na stwierdzenie, że możliwości rozwoju i modyfikacji algorytmów genetycznych są właściwie nieograniczone.

%TODO Zubert
%4350 linii kodu biblioteka wraz z selesman, 27 klas
%sama biblioteka 3060 linii kodu, 20 klas

\subsection{Perspektywy dalszego rozwoju aplikacji}
Zaimplementowana biblioteka stanowi podstawę, która może być rozwijana w przyszłości i stosowana do nowych zagadnień. Autor planuje implementację nowych metod selekcji osobników, a także nowego typu chromosomów - np. chromosomu reprezentującego macierz.
Możliwe jest także dodanie dodatkowych parametrów środowiska, np. zmienna liczba populacji lub wprowadzenie wieku chromosomów.

Bibliotekę będzie można łatwo dostosować do rozwiązywania innych problemów NP-zupełnych, np. problem plecakowy czy problem układania planu.

\pagebreak
%TODO wnioski stochastyczny / deterministyczny

%\begin{figure}[!ht]
%  \includegraphics[width=16cm, clip=true, trim=1cm 20cm 1cm 0cm]{../diagram_all}
%  \caption{Diagram klas sudoku}
%  \label{fig:diagram}
%\end{figure}


\begin{comment}
 



%TODO mpost magisterka.mp

  \begin{figure}
  \centering
  \begin{emp}[classdiag](20, 20)
  Class.A("A")()();
  Class.B("B")()();
  B.e = A.w + (-20, 0);
  drawObjects(A, B);
  link(inheritance)(B.e -- A.w);
  \end{emp}
  \caption{A class diagram}
  \end{figure}

  \begin{figure}
  \centering
  \begin{emp}[classdiag2](20, 20)
  save A; % This is important
  Class.A("A1")()();
  drawObject(A);
  \end{emp}
  \caption{Another class diagram}
  \end{figure}



  \begin{figure}
  \centering
  \begin{emp}[classdiag2](20, 20)

    Class.AbstractEnvironment("AbstractEnvironment")(
    "#solution:Chromosome*",
    "#chromosomeFactory:AbstractChromosomeFactory*",
    "#selectionStrategy:SelectionStrategy*",
    "#crossoverProb:double",
    "#mutationProb:double",
    "#additionalOperatorProb1:double",
    "#additionalOperatorProb2:double",
    "#abortWorseGenerations:bool",
    "#replaceWorstRepresentative:bool",
    "#addFreshChromosomesCount:int",
    "#removeDuplicatesMethod:int",
    "#maxGenerationsCount:int",
    "#bestFitness:double",
    "#timeElapsedSec:double",
    "#currentGeneration:Generation",
    "#populationSize:int",
    "#age:int",
    "#abortedGenerationsCount:int",
    "#performAdjustFitness:bool",
    "#finishConditionType:int")
    ("+AbstractEnvironment()",
    "+~AbstractEnvironment()",
    "+createPopulation(_populationSize:int)",
    "+setSelectionStrategy(_selectionStrategy:SelectionStrategy*)",
    "+setCrossoverProb(_crossoverProb:double)",
    "+setMutationProb(_mutationProb:double)",
    "+setAdditionalOperatorProb1(_additionalOperatorProb1:double)",
    "+setAdditionalOperatorProb2(_additionalOperatorProb2:double)",
    "+setAbortWorseGenerations(_abortWorseGenerations:bool)",
    "+setReplaceWorstRepresentative(_replaceWorstRepresentative:bool)",
    "+setAddFreshChromosomes(_addFreshChromosomes:int)",
    "+setRemoveDuplicatesMethod(_removeDuplicatesMethod:int)",
    "+setMaxGenerationsCount(_maxGenerationsCount:int)",
    "+setAdjustFitness(_adjustFitness:bool)",
    "+setFinishConditionType(_finishConditionType:int)",
    "+startSimulation()",
    "+getSolution():Chromosome*",
    "+getWorkingTimeSec():double",
    "+decodeChromosome(chrom:constChromosome&):QString",
    "+getStatisticsString():QString",
    "+setBestFitness(_bestFitness:double)",
    "+bestChromosomeFound():bool",
    "+getAge():int",
    "+getAbortedGenerationsCount():int",
    "+operator<<(dbg:QDebug,env:constAbstractEnvironment&):QDebug",
    "#countFitness(generation:Generation&)",
    "#adjustFitness(generation:Generation&)",
    "#scaleFitness(generation:Generation&)",
    "#removeDuplicates(generation:Generation&)",
    "#addFreshChromosomes(generation:Generation&)",
    "#fitnessFunction(chrom:Chromosome&)",
    "#finishCondition():bool",
    "#performReproduction():Generation",
    "#replaceGeneration(newGeneration:Generation");

  drawObject(AbstractEnvironment);
  \end{emp}
  \caption{Another class diagram}
  \end{figure}


  \begin{figure}
  \centering
  \begin{emp}[classdiag2](20, 20)
    Class.container("Container")("#x:int", "#y:int")("+CreateIterator()", "+Append(i:Item)");
    Class.client("Client")()();
    Class.iterator("Iterator")()("+First()", "-Next()", "#isDone()", "+CurrentItem()");
    Class.list("List")()();
    Class.vector("Vector")()();
    Class.listIterator("ListIterator")()("+First()", "+Next()", "+isDone()", "+CurrentItem()");
    Class.vectorIterator("VectorIterator")()();

    client.w = container.e + (40, 0);
    iterator.w = client.e + (70, 0);
    centered_allign_top(list, vector)(15, below(container.s, 60));
    centered_allign_top(listIterator, vectorIterator)(20, below(iterator.s, 60));

    drawObjects(container, client, iterator, list, vector, listIterator, vectorIterator);

    clink(associationUni)(client, container);
    clink(associationUni)(client, iterator);

    link(inheritance)(pathStepY(list.n, container.s, 30));
    link(inheritance)(pathStepY(vector.n - (7, 0), container.s, 30));

    link(inheritance)(pathStepY(listIterator.n, iterator.s, 30));
    link(inheritance)(pathStepY(vectorIterator.n, iterator.s, 30));

    link(associationUni)(pathStepY(listIterator.s - (10, 0), list.s + (10, 0), -45));
    link(associationUni)(pathStepY(list.s - (10, 0), listIterator.s + (10, 0), -110));

    link(associationUni)(pathStepY(vector.s - (10, 0), vectorIterator.s + (10, 0), -125));
    link(associationUni)(pathStepY(vectorIterator.s - (10, 0), vector.s + (10, 0), -70));

  \end{emp}
  \caption{Another class diagram}
  \end{figure}

  \begin{figure}

  %\centering
%\scalebox{0.5}{
  \begin{emp}[classdiag2](0, 0)
  %save A; % This is important

  %Class.A("A1")()();
iAssoc.iFont.scale := .5;



  Class.Chromosome("Chromosome")("+ minimize : bool", "# fitness : double")("+ ~ Chromosome()",
      "+ operator =(other : const Chromosome&) : Chromosome&",
      "+ setFitness(_fitness : double)",
      "+ getFitness() : double",
      "+ setRandom()",
      "+ crossOver(partner : const Chromosome&)",
      "+ mutate()",
      "+ mutate(index : int)",
      "+ additionalOperators(position : int)",
      "+ additionalOperators(second : const Chromosome&)",
      "+ operator <(other : const Chromosome&) : bool",
      "+ operator ==(other : const Chromosome&) : bool",
      "+ toString() : QString",
      "+ duplicate() : Chromosome*",
      "+ at(index : int) : QVariant",
      "+ data() : QVariant",
      "+ size() : int",
      "+ greaterThan(chr1 : const Chromosome*, chr2 : const Chromosome*) : bool",
      "+ operator <<(dbg : QDebug, chr : const Chromosome&) : QDebug",
      "# Chromosome()",
      "# Chromosome(other : const Chromosome&)");



  Class.VectorChromosome("VectorChromosome")("# geneArray : QList< T >", "# minValue : T", "# maxValue : T")("+ VectorChromosome()",
      "+ VectorChromosome(size : int)",
      "+ VectorChromosome(size : int, min : T, max : T)",
      "+ VectorChromosome(min : T, max : T)",
      "+ VectorChromosome(other : const VectorChromosome&)",
      "+ ~ VectorChromosome()",
      "+ operator =(other : const VectorChromosome< T >&) : VectorChromosome< T >&",
      "+ setRandom()",
      "+ crossOver(partner : const Chromosome&)",
      "+ mutate(index : int)",
      "+ operator ==(other : const Chromosome&) : bool",
      "+ at(index : int) : QVariant",
      "+ data() : QVariant",
      "+ size() : int",
      "# getRandomValue()");

  Class.BinaryChromosome("BinaryChromosome")("- bitArray : QBitArray")(
  "+ BinaryChromosome()",
  "+ BinaryChromosome(size : int)",
  "+ BinaryChromosome(other : const BinaryChromosome&)",
  "+ ~ BinaryChromosome()",
  "+ setRandom()",
  "+ crossOver(partner : const Chromosome&)",
  "+ mutate(index : int)",
  "+ operator ==(other : const Chromosome&) : bool",
  "+ toString() : QString",
  "+ duplicate() : Chromosome*",
  "+ at(index : int) : QVariant",
  "+ data() : QVariant",
  "+ size() : int");

  Class.IntegerChromosome("IntegerChromosome")("# numberArray : QList< int >",
  "- minValue : int",
  "- maxValue : int")("+ IntegerChromosome()",
  "+ IntegerChromosome(size : int)",
  "+ IntegerChromosome(size : int, min : int, max : int)",
  "+ IntegerChromosome(other : const IntegerChromosome&)",
  "+ ~ IntegerChromosome()",
  "+ setRandom()",
  "+ crossOver(partner : const Chromosome&)",
  "+ mutate(index : int)",
  "+ operator ==(other : const Chromosome&) : bool",
  "+ toString() : QString",
  "+ duplicate() : Chromosome*",
  "+ at(index : int) : QVariant",
  "+ data() : QVariant",
  "+ size() : int",
  "# getRandomIntegerValue() : int");

  Class.FloatChromosome("FloatChromosome")("- numberArray : QList< double >",
  "- minValue : double",
  "- maxValue : double")("+ FloatChromosome()",
  "+ FloatChromosome(size : int)",
  "+ FloatChromosome(other : const FloatChromosome&)",
  "+ ~ FloatChromosome()",
  "+ setRandom()",
  "+ crossOver(partner : const Chromosome&)",
  "+ mutate(index : int)",
  "+ operator ==(other : const Chromosome&) : bool",
  "+ toString() : QString",
  "+ duplicate() : Chromosome*",
  "+ at(index : int) : QVariant",
  "+ data() : QVariant",
  "+ size() : int",
  "- getRandomDoubleValue() : double");

  %VectorChromosome.ne = Chromosome.se + (0,-20);

  %BinaryChromosome.nw = VectorChromosome.ne + (5,0);

  %IntegerChromosome.n = VectorChromosome.s + (0,-20);
  %FloatChromosome.w = IntegerChromosome.e + (5,0);

  leftToRight(10)(VectorChromosome, BinaryChromosome);
leftToRight(10)(IntegerChromosome, FloatChromosome);

  topToBottom(10)(Chromosome, VectorChromosome, IntegerChromosome);

  %leftToRight(20)(BinaryChromosome, VectorChromosome);%IntegerChromosome, FloatChromosome);
  %topToBottom(20)(Chromosome, BinaryChromosome);%IntegerChromosome);

  %iClass.iFont.scale := .5;
  %iClass.info.iName.iFont.scale := .5;
  %Chromosome.info.iName.iFont.scale := .2;

Chromosome.info.iName.iFont.scale := .6;
Chromosome.info.iAttributeStack.iPict.iFont.scale := .6;
Chromosome.info.iMethodStack.iPict.iFont.scale := .6;

BinaryChromosome.info.iName.iFont.scale := .6;
BinaryChromosome.info.iAttributeStack.iPict.iFont.scale := .6;
BinaryChromosome.info.iMethodStack.iPict.iFont.scale := .6;

IntegerChromosome.info.iName.iFont.scale := .6;
IntegerChromosome.info.iAttributeStack.iPict.iFont.scale := .6;
IntegerChromosome.info.iMethodStack.iPict.iFont.scale := .6;

FloatChromosome.info.iName.iFont.scale := .6;
FloatChromosome.info.iAttributeStack.iPict.iFont.scale := .6;
FloatChromosome.info.iMethodStack.iPict.iFont.scale := .6;

VectorChromosome.info.iName.iFont.scale := .6;
VectorChromosome.info.iAttributeStack.iPict.iFont.scale := .6;
VectorChromosome.info.iMethodStack.iPict.iFont.scale := .6;

  %Chromosome.iFont.scale := .2;
  %iClass.foreColor := (.9, .9, 0);

iAssoc.iFont.scale := .5;


  %drawObject(A);
  drawObjects(Chromosome, VectorChromosome, BinaryChromosome, IntegerChromosome, FloatChromosome);
  \end{emp}
%}%scalebox
  \caption{chromosome}
  \end{figure}





%\scalebox{0.5}{
%\includegraphics{magisterka.5}
%}

\end{comment}

%skróty
\nomenclature{$n$}{liczebność populacji}
\nomenclature{$l$}{długość chromosomu}
\nomenclature{$k$}{liczba elementów alfabetu}
\nomenclature{$n_c$}{liczba ciągów kodowych}
\nomenclature{$n_s$}{liczba schematów}
\nomenclature{$f$}{funkcja oceny}
\nomenclature{$f_i$}{wartość funkcji oceny chromosomu $i$}
\nomenclature{$f_i'$}{przekształcona wartość funkcji oceny chromosomu $i$}
\nomenclature{$\bar{f}$}{średnia wartość funkcji oceny dla całej \glslink{populacja}{populacji} (średnie przystosowanie populacji)}
\nomenclature{$pMin_i$}{początek przedziału dystrybuanty dla chromosomu pomnożona przez 100 dla selekcji ruletkowej}
\nomenclature{$pMax_i$}{koniec przedziału dystrybuanty dla chromosomu pomnożona przez 100 dla selekcji ruletkowej}
\nomenclature{$e_i$}{oczekiwana liczba kopii danego chromosomu w kolejnym pokoleniu}
\nomenclature{$e_i'$}{ułamkowa część liczby $e_i$}
\nomenclature{$n_{t+1}$}{liczba kopii danego chromosomu, która wejdzie do nowego pokolenia po pierwszym kroku selekcji deterministycznej}
\nomenclature{$n_{t+1}'$}{liczba kopii danego chromosomu, która wejdzie do nowego pokolenia po drugim kroku selekcji deterministycznej}
\nomenclature{$s$}{schemat}
\nomenclature{$o(s)$}{rząd schematu}
\nomenclature{$\delta(s)$}{rozpiętość schematu}
\nomenclature{$p_c$}{prawdopodobieństwo krzyżowania}
\nomenclature{$p_m$}{prawdopodobieństwo mutacji}
\nomenclature{$p_s$}{prawdopodobieństwo dodatkowego operatora Sudoku}
\nomenclature{$m(s,t)$}{liczba reprezentantów schematu s (liczba chromosomów pasujących do schematu s) w populacji w chwili $t$}
\nomenclature{$p_{dc}$}{prawdopodobieństwo, że schemat nie przetrwa krzyżowania}
\nomenclature{$p_{sc}$}{prawdopodobieństwo, że schemat przetrwa krzyżowanie}
\nomenclature{$p_{sm}$}{prawdopodobieństwo, że schemat przetrwa mutację}
\nomenclature{$f(s,t)$}{średnie przystosowanie wszystkich chromosomów pasujących do schematu s w chwili $t$}
\nomenclature{$ts$}{rozmiar turnieju w selekcji turniejowej}
\nomenclature{$N_p$}{liczba przedziałów na jaką zostanie podzielony zakres argumentu $x$}
\nomenclature{$p_i$}{prawdopodobieństwo wybrania chromosomu do kolejnego pokolenia obliczane na podstawie wartości funkcji oceny}


%\newacronym{generacja}{pokolenie}{pppp}




%TODO makeglossaries magisterka

\let\stdsection\section
\def\section*#1{\stdsection{#1}}
\printglossaries
\label{sec:glossary}
\let\section\stdsection
%\pagebreak

\renewcommand{\lstlistlistingname}{Spis listingów}
\lstlistoflistings
\pagebreak

\listoffigures
\label{sec:listoffigures}
\pagebreak

\renewcommand\listtablename{Spis tabel}
\listoftables
\pagebreak

\bibliographystyle{plain}
\bibliography{bibliography.bib}
\end{empfile}%needed for UML metapost

\end{document}
